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
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.
- G. Bacsó, Zs. Tuza, Dominating cliques in \(P_5\)-free graphs, Period. Math. Hungar. 21 (1990) 3, 303-308.
- 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.
- M. Chudnovsky, The Erdős-Hajnal conjecture - a survey, J. Graph Theory 75 (2014), 178-190.
- M. Chudnovsky, N. Robertson, P. Seymour, R. Thomas, The strong perfect graph theorem, Ann. of Math. 164 (2006), 51-229.
- P. Erdős, Graph theory and probability, Canad. J. Math. 11 (1959), 34-38.
- L. Esperet, L. Lemoine, F. Maffray, G. Morel, The chromatic number of \(\{P_5,K_4\}\)-free graphs, Discrete Math. 313 (2013), 743-754.
- J.L. Fouquet, V. Giakoumakis, F. Maire, H. Thuillier, On graphs without \(P_5\) and \(\overline{P}_5\), Discrete Math. 146 (1995), 33-44.
- 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.
- I. Schiermeyer, Chromatic number of \(P_5\)-free graphs: Reed's conjecture, Discrete Math. 339 (2016) 7, 1940-1943.
- 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.
- Received: 2016-07-25.
- Accepted: 2016-11-09.
- Published online: 2017-04-28.
