Opuscula Mathematica
Opuscula Math. 37, no. 4 (2017), 609-615

On the chromatic number of (P<sub>5</sub>,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)
References ▼
  1. [1] G. Bacsó, Zs. Tuza, Dominating cliques in \(P_5\)-free graphs, Period. Math. Hungar. 21 (1990) 3, 303-308.
  2. [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. [3] M. Chudnovsky, The Erdős-Hajnal conjecture - a survey, J. Graph Theory 75 (2014), 178-190.
  4. [4] M. Chudnovsky, N. Robertson, P. Seymour, R. Thomas, The strong perfect graph theorem, Ann. of Math. 164 (2006), 51-229.
  5. [5] P. Erdős, Graph theory and probability, Canad. J. Math. 11 (1959), 34-38.
  6. [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. [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. [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. [9] I. Schiermeyer, Chromatic number of \(P_5\)-free graphs: Reed's conjecture, Discrete Math. 339 (2016) 7, 1940-1943.
  10. [10] S. Wagon, A bound on the chromatic number of graphs without certain induced subgraphs, J. Combin. Theory Ser. B 29 (1980), 345-346.
About the authors ▼
Ingo Schiermeyer
Technische Universität Bergakademie Freiberg, Institut für Diskrete Mathematik und Algebra, 09596 Freiberg, Germany
About the article ▼
Communicated by Hao Li.
Received: 2016-07-25.
Accepted: 2016-11-09.
Published online: 2017-04-28.
Cite this article as ▼
Ingo Schiermeyer, On the chromatic number of (P<sub>5</sub>,windmill)-free graphs, Opuscula Math. 37, no. 4 (2017), 609-615, http://dx.doi.org/10.7494/OpMath.2017.37.4.609.
Download this article's citation as: