کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
434007 | 689668 | 2015 | 10 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: Coloring clique-hypergraphs of graphs with no subdivision of K5K5 Coloring clique-hypergraphs of graphs with no subdivision of K5K5](/preview/png/434007.png)
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.
Journal: Theoretical Computer Science - Volume 592, 9 August 2015, Pages 166–175