Karthick, T.; Mishra, Suchismita On the chromatic number of (\(P_6\), diamond)-free graphs. (English) Zbl 1397.05066 Graphs Comb. 34, No. 4, 677-692 (2018). Summary: In this paper, we first show that every (\(P_6\), diamond, \(K_4\))-free graph is 6-colorable. We also give an example of a (\(P_6\), diamond, \(K_4\))-free graph \(G\) with \(\chi (G)\)\( = 6\). Further, we show that for every (\(P_6\), diamond)-free graph \(G\), the chromatic number of \(G\) is upper bounded by a linear function of its clique number. This generalizes some known results in the literature. Cited in 7 Documents MSC: 05C15 Coloring of graphs and hypergraphs Keywords:graph classes; \(P_6\)-free graphs; diamond-free graphs; chromatic number; clique number PDFBibTeX XMLCite \textit{T. Karthick} and \textit{S. Mishra}, Graphs Comb. 34, No. 4, 677--692 (2018; Zbl 1397.05066) Full Text: DOI References: [1] Addario-Berry, L; Chudnovsky, M; Havet, F; Reed, B; Seymour, P, Bisimplicial vertices in even-hole-free graphs, J. Combin. Theory Ser. B, 98, 1119-1164, (2008) · Zbl 1205.05119 · doi:10.1016/j.jctb.2007.12.006 [2] Bharathi, AP; Choudum, SA, Colouring of \(P_2∪ P_3\)-free graphs, Graphs Combin., 34, 97-107, (2018) · Zbl 1390.05062 · doi:10.1007/s00373-017-1870-8 [3] Blanche, A., Dabrowski, K. K., Johnson, M., Paulusma, D.: Hereditary graph Classes: when the complexities of colouring and clique cover coincide. arXiv:1607.06757v3 (2017) · Zbl 1417.05060 [4] Brandstädt, A; Giakoumakis, V; Maffray, F, Clique separator decomposition of hole-free and diamond-free graphs and algorithmic consequences, Disc. Appl. Math., 160, 471-478, (2012) · Zbl 1236.05127 · doi:10.1016/j.dam.2011.10.031 [5] Brandt, S, Triangle-free graphs and forbidden subgraphs, Disc. Appl. Math., 120, 25-33, (2002) · Zbl 1003.05039 · doi:10.1016/S0166-218X(01)00277-3 [6] Broersma, HJ; Golovach, PA; Paulusma, D; Song, J, Updating the complexity status of coloring graphs without a fixed induced linear forest, Theoret. Comput. Sci., 414, 9-19, (2012) · Zbl 1234.68129 · doi:10.1016/j.tcs.2011.10.005 [7] Choudum, SA; Karthick, T, Maximal cliques in \(P_2 ∪ P_3, C_4\)-free graphs, Disc. Math., 310, 3398-3403, (2010) · Zbl 1221.05258 · doi:10.1016/j.disc.2010.08.005 [8] Choudum, SA; Karthick, T; Shalu, MA, Perfect coloring and linearly \(χ \)-bound \(P_6\)-free graphs, J. Graph Theory, 54, 293-306, (2007) · Zbl 1121.05045 · doi:10.1002/jgt.20212 [9] Chudnovsky, M; Goedgebeur, J; Schaudt, O; Zhong, M, Obstructions for three-coloring graphs without induced paths on six vertices, Proc. SODA, 2016, 1774-1783, (2016) · Zbl 1410.05063 [10] Chudnovsky, M; Seymour, P; Robertson, N; Thomas, R, The strong perfect graph theorem, Ann. Math., 164, 51-229, (2006) · Zbl 1112.05042 · doi:10.4007/annals.2006.164.51 [11] Chudnovsky, M; Seymour, P; Robertson, N; Thomas, R, \(K_4\)-free graphs with no odd holes, J. Combin. Theory Ser. B, 100, 313-331, (2010) · Zbl 1274.05238 · doi:10.1016/j.jctb.2009.10.001 [12] Chudnovsky, M., Spirkl, S., Zhong, M.: Four-coloring \(P_6\)-free graphs. I. Extending an excellent precoloring, arXiv:1802.02282v2 [math.CO] (2018) · Zbl 1342.05040 [13] Chudnovsky, M., Spirkl, S., Zhong, M.: Four-coloring \(P_6\)-free graphs. II. Finding an excellent precoloring, arXiv:1802.02283v2 [math.CO] (2018) [14] Dabrowski, K. K., Dross, F., Paulusma, D.: Colouring diamond-free graphs. In: 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016), Rasmus Pagh Ed., LIPICS, Article No. 16; pp. 16:1-16:14 · Zbl 1378.68070 [15] Esperet, L; Lemoine, L; Maffray, F; Morel, M, The chromatic number of \(P_5, K_4\)-free graphs, Disc. Math., 313, 743-754, (2013) · Zbl 1260.05056 · doi:10.1016/j.disc.2012.12.019 [16] Fan, G; Xu, B; Ye, T; Yu, X, Forbidden subgraphs and \(3\)-colorings, SIAM J. Disc. Math., 28, 1226-1256, (2014) · Zbl 1305.05075 · doi:10.1137/120895834 [17] Golovach, PA; Johnson, M; Paulusma, D; Song, J, A survey on the computational complexity of colouring graphs with forbidden subgraphs, J. Graph Theory, 84, 331-363, (2017) · Zbl 1359.05039 · doi:10.1002/jgt.22028 [18] Golumbic, M.C.: Algorithmic Graph Theory and Perfect Graphs, Annals of Discrete Mathematics, 2nd edn. Elsevier, Amsterdam (2004) · Zbl 1050.05002 [19] Gravier, S; Hoàng, CT; Maffray, F, Coloring the hypergraph of maximal cliques of a graph with no long path, Disc. Math., 272, 285-290, (2003) · Zbl 1028.05033 · doi:10.1016/S0012-365X(03)00197-3 [20] Gyárfás, A, Problems from the world surrounding perfect graphs, Zastosowania Matematyki Applicationes Mathematicae, 19, 413-441, (1987) · Zbl 0718.05041 · doi:10.4064/am-19-3-4-413-441 [21] Huang, S, Improved complexity results on \(k\)-coloring \(P_t\)-free graphs, Eur. J. Combin., 51, 336-346, (2016) · Zbl 1321.05085 · doi:10.1016/j.ejc.2015.06.005 [22] Karp, R.M.: Reducibility among combinatorial problems. In: Miller, R.E., Thatcher, J.W., editors, Complexity of computer computations. Plenum, New York, pp. 85-103 (1972) · Zbl 1467.68065 [23] Karthick, T.: Vertex coloring and cliques of certain \(P_6\)-free graphs and claw-free graphs. Ph.D. Thesis, IIT Madras (2010) [24] Karthick, T; Maffray, F, Vizing bound for the chromatic number on some graph classes, Graphs Combin., 32, 1447-1460, (2016) · Zbl 1342.05040 · doi:10.1007/s00373-015-1651-1 [25] Kloks, T; Müller, H; Vušković, K, Even-hole-free graphs that do not contain diamonds: a structure theorem and its consequences, J. Combin. Theory. Ser. B, 99, 733-800, (2009) · Zbl 1218.05160 · doi:10.1016/j.jctb.2008.12.005 [26] Kral, D., Kratochvil, J., Tuza, Z.S., Woeginger, G.J.: Complexity of coloring graphs without forbidden induced subgraphs. In: Proceedings of WG 2001, Lecture Notes in Computer Science 2204, 254-262 (2001) · Zbl 1042.68639 [27] Mosca, R, Independent sets in (\(P_6\), diamond)-free graphs, Disc. Math. Theoret. Comput. Sci., 11, 125-140, (2009) · Zbl 1196.05065 [28] Mycielski, J, Sur le coloriage des graphes, Colloq. Math., 3, 161-162, (1955) · Zbl 0064.17805 · doi:10.4064/cm-3-2-161-162 [29] Pyatkin, AV, Triangle-free \(2P_3\)-free graphs are \(4\)-colorable, Disc. Math., 313, 715-720, (2013) · Zbl 1259.05066 · doi:10.1016/j.disc.2012.10.019 [30] Randerath, B; Schiermeyer, I, \(3\)-colorability \(∈ \cal{P}\) for \(P_6\)-free graphs, Disc. Appl. Math., 136, 299-313, (2004) · Zbl 1035.05042 · doi:10.1016/S0166-218X(03)00446-3 [31] Randerath, B; Schiermeyer, I, Vertex colouring and forbidden subgraphs: a survey, Graphs Combin., 20, 1-40, (2004) · Zbl 1056.05065 · doi:10.1007/s00373-003-0540-1 [32] Randerath, B; Schiermeyer, I; Tewes, M, Three-colourability and forbidden subgraphs. II: polynomial algorithms, Disc. Math., 251, 137-153, (2002) · Zbl 0999.05042 · doi:10.1016/S0012-365X(01)00335-1 [33] Tucker, A, Coloring perfect \((K_4 -e)\)-free graphs, J. Combin. Theory Ser. B, 42, 313-318, (1987) · Zbl 0585.05007 · doi:10.1016/0095-8956(87)90048-7 [34] West, D.B.: Introduction to Graph Theory, 2nd edn. Prentice-Hall, Englewood Cliffs, New Jersey (2000) This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.