B. Aspvall, M. Plass, R. Tarjan, A Linear-Time Algorithm for Testing the Truth of Certain Quantified Boolean Formulas, Inf. Process. Lett. 8 (3) (1979), 121-123. [OpenAIRE]
 F. Bonomo, M. Chudnovsky, P. Maceli, O. Schaudt, M. Stein and M. Zhong, Threecoloring graphs without triangles or induced paths on seven vertices, submitted for publication.
 M. Chudnovsky, P. Maceli and M. Zhong, Three-coloring graphs with no induced six-edge path I : the triangle-free case, manuscript.
 K. Edwards, The complexity of colouring problems on dense graphs, Theoret. Comput. Sci. 43 (1986), 337-343.
 C.T. Hoa`ng, M. Kamin´ski, V.V. Lozin, J. Sawada and X. Shu, Deciding k-colorability of P5-free graphs in polynomial time, Algorithmica 57 (2010), 74-81.
 I. Holyer, The NP-completeness of edge coloring, SIAM J. Comput. 10 (1981), 718- 720. [OpenAIRE]
 S. Huang, Improved Complexity Results on k-Coloring Pt-Free Graphs, Proc. MFCS 2013, LNCS, to appear.
 M. Kamin´ski and V.V. Lozin, Coloring edges and vertices of graphs without short or long cycles. Contrib. Discrete Mah. 2 (2007), 61-66.
 R. M. Karp, Reducibility Among Combinatorial Problems, Complexity of Computer Computations, New York: Plenum., 85-103.
 D. Kr´al, J. Kratochv´ıl, Z. Tuza, and G. Woeginger, Complexity of coloring graphs without forbidden induced subgraphs, Proceedings of WG 2001, LNCS 2204, 254-262. [OpenAIRE]
 D. Leven and Z. Galil, NP-completeness of finding the chromatic index of regular graphs. J. Algorithm 4 (1983), 35-44. [OpenAIRE]
 B. Randerath and I. Schiermeyer, 3-Colorability ∈ P for P6-free graphs, Discrete Appl. Math. 136 (2004), 299-313. [OpenAIRE]
 B. Randerath, I. Schiermeyer and M.Tewes, Three-colorability and forbidden subgraphs. II: polynomial algorithms, Discrete Mathematics 251 (2002), 137153. [OpenAIRE]
 J. Stacho, private communication.
 L. Stockmeyer, Planar 3-colorability is polynomial complete, SIGACT News (1973), 19-25.