Coloring clique-hypergraphs of graphs with no subdivision of K5K5

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.