More Results on Clique-chromatic Numbers of Graphs with No Long Path - Discrete and Computational Geometry and Graphs - page 189

Since the 4-chromatic Mycielski's graph G 4 is ( P 3 +3 P 1 , diamond)-free, the
upper bound in Theorem 6 for the case k = 3 is sharp.
References
1. Bacso, G., Gravier, S., Gyarfas, A., Preissmann, M., Sebo, A.: Coloring the maximal
cliques of graphs. SIAM J. Discrete Math. 17 , 361-376 (2004)
2. Campos, C.N., Dantasa, S., de Mello, C.P.: Colouring clique-hypergraphs of circu-
lant graphs. Electron. Notes Discrete Math. 30 , 189-194 (2008)
3. Defossez, D.: Clique-coloring some classes of odd-hole-free. J. Graph Theory 53 ,
233-249 (2006)
4. Duffus, D., Sands, B., Sauer, N., Woodrow, R.E.: Two-coloring all two-element
maximal antichains. J. Comb. Theory Ser. A 57 , 109-116 (1991)
5. Duffus, D., Kierstead, H.A., Trotter, W.T.: Fibres and ordered set coloring. J. Comb.
Theory Ser. A 58 , 158-164 (1991)
6. Gravier, S., Hoang, C.T., Maffray, F.: Coloring the hypergraph of maximal cliques
of a graph with no long path. Discrete Math. 272 , 285-290 (2003)
7. Gravier, S., Skrekovski, R.: Coloring the clique hypergraph of graphs without for-
bidden structure, Les cahiers du laboratoire Leibniz 83 , (2003). http://www-leibniz.
imag.fr/LesCahiers/
8. Mycielski, J.: Sur le coloriage des graphes. J. Colloq. Math. 3 , 161-162 (1955)
9. West, D.B.: Introduction to Graph Theory. Prentice Hall, New Jersey (2001)