| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 4652685 | Electronic Notes in Discrete Mathematics | 2008 | 6 Pages |
We consider the clique-coloring problem, that is, coloring the vertices of a given graph such that no maximal clique of size at least two is monocolored. More specifically, we investigate the problem of giving a class of graphs, to determine if there exists a constant C such that every graph in this class is C-clique-colorable. We consider the classes of UE and UEH graphs.A graph G is called an UE graph if it is the edge intersection graph of a family of paths in a tree. If this family satisfies the Helly Property we say that G is an UEH graph.We show that every UEH graph is 3-clique-colorable. Moreover our proof is constructive and provides a polynomial-time algorithm. We also describe, for each k≥2, an UE graph that is not k-clique-colorable. The UE graphs form one of the few known classes for which the clique-chromatic number is unbounded.
