Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
434007 | Theoretical Computer Science | 2015 | 10 Pages |
A clique-coloring of a graph G is a coloring of the vertices of G so that no maximal clique of size at least two is monochromatic. The clique-hypergraph, H(G)H(G), of a graph G has V(G)V(G) as its set of vertices and the maximal cliques of G as its hyperedges. A (vertex) coloring of H(G)H(G) with no monochromatic hyperedge is a clique-coloring of G. The clique-chromatic number of G is the least number of colors for which G admits a clique-coloring. Every planar graph has been proved to be 3-clique-colorable and every claw-free planar graph, different from an odd cycle, has been proved to be 2-clique-colorable. In this paper we first generalize the result of planar graphs to K5K5-minor-free graphs. Furthermore, we generalize the result of claw-free planar graphs to K5K5-subdivision-free graphs and give a polynomial-time algorithm to find a 2-clique-coloring of K5K5-subdivision-free graphs.