Edge-Clique Graphs and the Lambda-Coloring Problem

T. Calamoneri and R. Petreschi

Abstract

This paper deals with edge-clique graphs and with the Lambda-coloring problem when restricted to this class.

A characterization of edge-clique graphs of outerplanar graphs is given; a complete description of edge-clique graphs of threshold graphs is presented and a linear time algorithm for Lambda-coloring the edge-clique graph of a threshold graph is provided. A survey on the Lambda$-coloring problem, when restricted to edge-clique graphs, is reported.

TEXT AND PDF Files

Journal Version