Research ArticleOpen AccessGoogle Scholar indexed
On the Chromatic Number of (<i>P</i><sub>5</sub>, <i>C</i><sub>5</sub>, Cricket)-Free Graphs
School of Mathematics and Statistics, Shandong Normal University, Jinan, China
- 1 School of Mathematics and Statistics, Shandong Normal University, Jinan, China
Copy link · social · email
Abstract
For a graph G, let be the chromatic number of G. It is well-known that holds for any graph G with clique number . For a hereditary graph class , whether there exists a function f such that holds for every has been widely studied. Moreover, the form of minimum such an f is also concerned. A result of Schiermeyer shows that every -free graph G with clique number has . Chudnovsky and Sivaraman proved that every -free with clique number graph is -colorable. In this paper, for any -free graph G with clique number , we prove that . The main methods in the proof are set partition and induction.
Keywords<i>P</i><sub>5</sub>-Free GraphsChromatic Number<i>X</i>-Boundedness
- Chudnovsky, M., Robertson, N., Seymour, P. and Thomas, R. (2006) The Strong Perfect Graph Theorem. Annals of Mathematic, 164, 51-229. https://doi.org/10.4007/annals.2006.164.51
- Erdös, P. (1959) Graph Theory and Probability. Classic Papers in Combinatorics, 11, 34-38. https://doi.org/10.4153/CJM-1959-003-9
- Gyárfás, A. (1987) Problems from the World Surrounding Perfect Graphs. Applicationes Mathematicae, 19, 413-441. https://doi.org/10.4064/am-19-3-4-413-441
- Esperet, L., Lemoine, L., Maffray, F. and Morel, G. (2013) The Chromatic Number of (P5, K4)-Free Graphs. Discrete Mathematics, 313, 743-754. https://doi.org/10.1016/j.disc.2012.12.019
- Randerath, B. and Schiermeyer, I. (2004) Vertex Colouring and Forbidden Subgraphs—A Survey. Graphs and Combinatorics, 20, 1-40. https://doi.org/10.1007/s00373-003-0540-1
- Chudnovsky, M., Karthick, T., Maceli, P. and Maffray, F. (2020) Coloring Graphs with No Induced Five-Vertex Path or Gem. Journal of Graph Theory, 95, 527-542. https://doi.org/10.1002/jgt.22572
- Huang, S. and Karthick, T. (2021) On Graphs with No Induced Five-Vertex Path or Paraglider. Journal of Graph Theory, 97, 305-323. https://doi.org/10.1002/jgt.22656
- Karthick, T. and Maffray, F. (2016) Vizing Bound for the Chromatic Number on Some Graph Classes. Graphs and Combinatorics, 32, 1447-1460. https://doi.org/10.1007/s00373-015-1651-1
- Randerath, B. (1998) The Vizing Bound for the Chromatic Number Based on Forbidden Pairs. Ph.D. Thesis, RWTH Aachen, Shaker Verlag.
- Brause, C., Randerath, B., Schiermeyer, I. and Vumar, E. (2019) On the Chromatic Number of 2K2-Free Graphs. Discrete Applied Mathematics, 253, 14-24. https://doi.org/10.1016/j.dam.2018.09.030
- Chudnovsky, M. and Sivaraman, V. (2019) Perfect Divisibility and 2-Divisibility. Journal of Graph Theory, 90, 54-60. https://doi.org/10.1002/jgt.22367
- Fouquet, J., Giakoumakis, V., Maire, F. and Thuillier, H. (1995) On Graphs without P5 and P5. Discrete Mathematics, 146, 33-44. https://doi.org/10.1016/0012-365X(94)00155-X
- Schiermeyer, I. (2016) Chromatic Number of P5-Free Graphs: Reed’s Conjecture. Discrete Mathematics, 339, 1940-1943. https://doi.org/10.1016/j.disc.2015.11.020
- Brause, C., Doan, T. and Schiermeyer, I. (2016) On the Chromatic Number of (P5, K2,t)-Free Graphs. Electronic Notes in Discrete Mathematics, 55, 127-130. https://doi.org/10.1016/j.endm.2016.10.032