publication . Preprint . 2015

Obstructions for three-coloring graphs without induced paths on six vertices

Chudnovsky, Maria; Goedgebeur, Jan; Schaudt, Oliver; Zhong, Mingxian;
Open Access English
  • Published: 27 Apr 2015
Comment: 31 pages
free text keywords: Mathematics - Combinatorics, Computer Science - Discrete Mathematics
Related Organizations
Funded by
NSF| Collaborative Research: cliques, stable sets and approximate structure
  • Funder: National Science Foundation (NSF)
  • Project Code: 1265803
  • Funding stream: Directorate for Mathematical & Physical Sciences | Division of Mathematical Sciences
Download from
18 references, page 1 of 2

[1] G. Brinkmann, K. Coolsaet, J. Goedgebeur, and H. Melot, House of Graphs: a database of interesting graphs, Discrete Applied Mathematics 161 (2013), no. 1-2, 311{314, Available at http://hog.

[2] D. Bruce, C.T. Hoang, and J. Sawada, A certifying algorithm for 3-colorability of P5-free graphs, Proceedings of the 20th International Symposium on Algorithms and Computation, Springer-Verlag, 2009, pp. 594{604.

[3] M. Chudnovsky, P. Maceli, and M. Zhong, Three-coloring graphs with no induced path on seven vertices II: using a triangle, Submitted.

[4] M. Chudnovsky, N. Robertson, P. Seymour, and R. Thomas, The Strong Perfect Graph Theorem, Annals of Mathematics 164 (2006), no. 1, 51{229.

[5] P. Erd}os, Graph theory and probability, Canad. J. Math. 11 (1959), 34{38.

[6] J. Goedgebeur, Homepage of generator for 4-critical Pt-free graphs: criticalpfree/.

[7] , Homepage of generator for 4-critical Pt-free 1-vertex extensions of tripods: http://caagt.

[8] J. Goedgebeur and O. Schaudt, Exhaustive generation of k-critical H-free graphs, in preparation.

[9] P.A. Golovach, M. Johnson, D. Paulusma, and J. Song, A survey on the computational complexity of colouring graphs with forbidden subgraphs, arXiv:1407.1482v4 [cs.CC].

[10] P. Hell and S. Huang, Complexity of coloring graphs without paths and cycles, LATIN 2014: Theoretical Informatics, Springer, 2014, pp. 538{549.

[11] C.T. Hoang, B. Moore, D. Recoskie, J. Sawada, and M. Vatshelle, Constructions of k-critical P5-free graphs, Disc. App. Math. 182 (2015), 91{98.

[12] F. Lazebnik and V.A. Ustimenkob, Explicit construction of graphs with an arbitrary large girth and of large size, Disc. App. Math. 60 (1995), 275{284. [OpenAIRE]

[13] B.D. McKay, nauty User's Guide (Version 2.5), Technical Report TR-CS-90-02, Department of Computer Science, Australian National University. The latest version of the software is available at

[14] B.D. McKay and A. Piperno, Practical graph isomorphism, II, Journal of Symbolic Computation 60 (2014), 94{112.

[15] A. Pokrovskiy, private communication.

18 references, page 1 of 2
Powered by OpenAIRE Research Graph
Any information missing or wrong?Report an Issue