Opuscula Math. 37, no. 4 (2017), 609-615
http://dx.doi.org/10.7494/OpMath.2017.37.4.609

Opuscula Mathematica

On the chromatic number of (P5,windmill)-free graphs

Ingo Schiermeyer

Abstract. In this paper we study the chromatic number of $$(P_5, windmill)$$-free graphs. For integers $$r,p\geq 2$$ the windmill graph $$W_{r+1}^p=K_1 \vee pK_r$$ is the graph obtained by joining a single vertex (the center) to the vertices of $$p$$ disjoint copies of a complete graph $$K_r$$. Our main result is that every $$(P_5, windmill)$$-free graph $$G$$ admits a polynomial $$\chi$$-binding function. Moreover, we will present polynomial $$\chi$$-binding functions for several other subclasses of $$P_5$$-free graphs.

Keywords: vertex colouring, perfect graphs, $$\chi$$-binding function, forbidden induced subgraph.

Mathematics Subject Classification: 05C15, 05C17.

Full text (pdf)

1. G. Bacsó, Zs. Tuza, Dominating cliques in $$P_5$$-free graphs, Period. Math. Hungar. 21 (1990) 3, 303-308.
2. S.A. Choudum, T. Karthick, M.A. Shalu, Perfect coloring and linearly $$\chi$$-bound $$P_6$$-free graphs, J. Graph Theory 54 (2006) 4, 293-306.
3. M. Chudnovsky, The Erdős-Hajnal conjecture - a survey, J. Graph Theory 75 (2014), 178-190.
4. M. Chudnovsky, N. Robertson, P. Seymour, R. Thomas, The strong perfect graph theorem, Ann. of Math. 164 (2006), 51-229.
5. P. Erdős, Graph theory and probability, Canad. J. Math. 11 (1959), 34-38.
6. L. Esperet, L. Lemoine, F. Maffray, G. Morel, The chromatic number of $$\{P_5,K_4\}$$-free graphs, Discrete Math. 313 (2013), 743-754.
7. J.L. Fouquet, V. Giakoumakis, F. Maire, H. Thuillier, On graphs without $$P_5$$ and $$\overline{P}_5$$, Discrete Math. 146 (1995), 33-44.
8. A. Gyárfás, Problems from the world surrounding perfect graphs, [in:] Proc. Int. Conf. on Comb. Analysis and Applications, Pokrzywna, 1985; Zastos. Mat. 19 (1987), 413-441.
9. I. Schiermeyer, Chromatic number of $$P_5$$-free graphs: Reed's conjecture, Discrete Math. 339 (2016) 7, 1940-1943.
10. S. Wagon, A bound on the chromatic number of graphs without certain induced subgraphs, J. Combin. Theory Ser. B 29 (1980), 345-346.
• Ingo Schiermeyer
• Technische Universität Bergakademie Freiberg, Institut für Diskrete Mathematik und Algebra, 09596 Freiberg, Germany
• Communicated by Hao Li.
• Accepted: 2016-11-09.
• Published online: 2017-04-28.