On color-critical (\(P_5\),\(\operatorname{co-}P_5\))-free graphs. (English) Zbl 1350.05032
Summary: A graph is \(k\)-critical if it is \(k\)-chromatic but each of its proper induced subgraphs is \((k-1)\)-colorable. It is known that the number of 4-critical \(P_5\)-free graphs is finite, but there is an infinite number of \(k\)-critical \(P_5\)-free graphs for each \(k \geq 5\). We show that the number of \(k\)-critical \((P_5, \overline{P}_5)\)-free graphs is finite for every fixed \(k\). Our result implies the existence of a certifying algorithm for \(k\)-coloring \((P_5, \overline{P}_5)\)-free graphs.
MSC:
| 05C15 | Coloring of graphs and hypergraphs |
References:
| [1] | Bruce, D.; Hoàng, C. T.; Sawada, J., A certifying algorithm for 3-colorability of \(P_5\)-free graphs, Lecture Notes in Comput. Sci., 5878, 594-604 (2009) · Zbl 1272.05191 |
| [2] | Chvátal, V.; Hoàng, C. T.; Mahadev, N. V.R.; De Werra, D., Four classes of perfectly orderable graphs, J. Graph Theory, 11, 4, 481-495 (1987) · Zbl 0654.05032 |
| [3] | Fouquet, J.-L.; Giakoumakis, V.; Maire, F.; Thuillier, H., On graphs without \(P_5\) and \(\overline{P_5} \), Discrete Math., 146, 1-3, 33-44 (1995) · Zbl 0837.05095 |
| [4] | Giakoumakis, V.; Rusu, I., Weighted parameters in \((P_5, \overline{P_5})\)-free graphs, Discrete Appl. Math, 80, 255-261 (1997) · Zbl 0903.05045 |
| [5] | Hoàng, C. T.; Kamiński, M.; Lozin, V.; Sawada, J.; Shu, X., A note on \(k\)-colourability of \(P_5\)-free graphs, Lecture Notes in Comput. Sci., 5162, 387-394 (2008) · Zbl 1173.05351 |
| [6] | Hoàng, C. T.; Kamiński, M.; Lozin, V. V.; Sawada, J.; Shu, X., Deciding \(k\)-colorability of \(P_5\)-free graphs in polynomial time, Algorithmica, 57, 1, 74-81 (2010) · Zbl 1222.68083 |
| [7] | Hoàng, C. T.; Lazzarato, D. A., Polynomial-time algorithms for minimum weighted colorings of \((P_5, \overline{P}_5)\)-free graphs and related graph classes, Discrete Appl. Math., 186, 106-111 (2015) · Zbl 1311.05064 |
| [8] | Hoàng, C. T.; Moore, B.; Recoskie, D.; Sawada, J., On \(k\)-critical \(P_5\)-free graphs, Proceedings of the VII Latin-American Algorithms, Graphs, and Optimization Symposium. Proceedings of the VII Latin-American Algorithms, Graphs, and Optimization Symposium, LAGOS 2013. Proceedings of the VII Latin-American Algorithms, Graphs, and Optimization Symposium. Proceedings of the VII Latin-American Algorithms, Graphs, and Optimization Symposium, LAGOS 2013, Electron. Notes Discrete Math., 44, 187-193 (2013) |
| [9] | Knuth, D. E., Mathematics and computer science: coping with finiteness, Science, 194, 4271, 1235-1242 (1976) · Zbl 1225.68001 |
| [10] | Kratochvíl, J.; Král, D.; Tuza, Zs.; Woeginger, G. J., Complexity of coloring graphs without forbidden induced subgraphs, Lecture Notes in Comput. Sci., 2204, 254-262 (2001) · Zbl 1042.68639 |
| [11] | Maffray, F.; Morel, G., On 3-colorable \(P_5\)-free graphs, SIAM J. Discrete Math., 26, 1682-1708 (2012) · Zbl 1261.05030 |
| [12] | Randerath, B.; Schiermeyer, I., 3-colorability \(\in P\) for \(P_6\)-free graphs, Discrete Appl. Math., 136, 299-313 (2004) · Zbl 1035.05042 |
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.
