F. Bonomo, M. Chudnovsky, P. Maceli, O. Schaudt, M. Stein, and M. Zhong, Threecoloring and list three-coloring graphs without induced paths on seven vertices, Combinatorica, 38 (2018), pp. 779-801.
G. Brinkmann, K. Coolsaet, J. Goedgebeur, and H. Melot, House of graphs: A database of interesting graphs, Discrete Appl. Math., 161 (2013), pp. 311-314; available at http: //hog.grinvin.org/.
D. Bruce, C. T. Hoang, and J. Sawada, A certifying algorithm for 3-colorability of P5-free graphs, in Proceedings of the 20th International Symposium on Algorithms and Computation, Springer-Verlag, 2009, pp. 594-604.
E. Camby and O. Schaudt, A new characterization of Pk-free graphs, Algorithmica, 75 (2016), pp. 205-217.
M. Chudnovsky, J. Goedgebeur, O. Schaudt, and M. Zhong, Obstructions for threecoloring graphs with one forbidden induced subgraph, in Proceedings of the TwentySeventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, SIAM, 2016, pp. 1774-1783, https://doi.org/10.1137/1.9781611974331.ch123.
M. Chudnovsky, J. Goedgebeur, O. Schaudt, and M. Zhong, Obstructions for threecoloring graphs without induced paths on six vertices, J. Combin. Theory Ser. B, 140 (2020), pp. 45-83.
P. Erdos, Graph theory and probability, Canad. J. Math., 11 (1959), pp. 34-38.
F. Galvin, I. Rival, and B. Sands, A Ramsey-type theorem for traceable graphs, J. Combin. Theory Ser. B, 33 (1982), pp. 7-16.
J. Goedgebeur, Homepage of Generator for Obstructions against List-3 Colorability, https: //caagt.ugent.be/listcriticalpfree/.
J. Goedgebeur and O. Schaudt, Exhaustive generation of k-critical H -free graphs, J. Graph Theory, 87 (2018), pp. 188-207.
P. A. Golovach, M. Johnson, D. Paulusma, and J. Song, A survey on the computational complexity of coloring graphs with forbidden subgraphs, J. Graph Theory, 84 (2017), pp. 331-363.
P. Hell and S. Huang, Complexity of coloring graphs without paths and cycles, Discrete Appl. Math., 216, Part 1 (2017), pp. 211-232.
C. T. Hoang, B. Moore, D. Recoskie, J. Sawada, and M. Vatshelle, Constructions of k-critical P5-free graphs, Discrete Appl. Math., 182 (2015), pp. 91-98.
I. Holyer, The NP-completeness of edge-coloring, SIAM J. Comput., 10 (1981), pp. 718-720, https://doi.org/10.1137/0210055.
B. M. P. Jansen and S. Kratsch, Data reduction for graph coloring problems, Inform. and Comput., 231 (2013), pp. 70-88.
M. Kaminski and V. V. Lozin, Coloring edges and vertices of graphs without short or long cycles, Contrib. Discrete Math., 2 (2007), pp. 61-66.
D. Kral', J. Kratochvíl, Zs. Tuza, and G. J. Woeginger, Complexity of coloring graphs without forbidden induced subgraphs, in Proceedings of the International Workshop on Graph-Theoretic Concepts in Computer Science 2001, A. Brandstadt and V. B. Le, eds., Lecture Notes in Comput. Sci. 2204, Springer, 2001, pp. 254-262.
F. Lazebnik and V. A. Ustimenko, Explicit construction of graphs with an arbitrary large girth and of large size, Discrete Appl. Math., 60 (1995), pp. 275-284.
D. Leven and Z. Galil, NP-completeness of finding the chromatic index of regular graphs, J. Algorithms, 4 (1983), pp. 35-44.
F. Maffray and G. Morel, On 3-colorable P5-free graphs, SIAM J. Discrete Math., 26 (2012), pp. 1682-1708, https://doi.org/10.1137/110829222.
A. Pokrovskiy, private communication.
F. P. Ramsey, On a problem of formal logic, Proc. London Math. Soc. (2), 30 (1930), pp. 264-286.
B. Randerath and I. Schiermeyer, 3-colorabilityin P for P6-free graphs, Discrete Appl. Math., 136 (2004), pp. 299-313.
D. Scheische, On a property of the class of n-colorable graphs, J. Combin. Theory Ser. B, 16 (1974), pp. 191-193.
P. Seymour, Barbados Workshop on Graph Coloring and Structure, 2014.
E. Zhang, Bounded Obstructions for Three-coloring Graphs with Lists of Size Two, Senior Thesis, Princeton University, 2017.
