publication . Preprint . 2015

Three-coloring graphs with no induced seven-vertex path II : using a triangle

Chudnovsky, Maria; Maceli, Peter; Zhong, Mingxian;
Open Access English
  • Published: 11 Mar 2015
Comment: 26 pages
ACM Computing Classification System: MathematicsofComputing_DISCRETEMATHEMATICSComputingMethodologies_COMPUTERGRAPHICSTheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY
free text keywords: Computer Science - Discrete Mathematics, Mathematics - Combinatorics
Related Organizations
Funded by
NSF| Coloring and Structure
  • Funder: National Science Foundation (NSF)
  • Project Code: 1001091
  • Funding stream: Directorate for Mathematical & Physical Sciences | Division of Mathematical Sciences
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
NSF| RI: Small: Learning and Inference with Perfect Graphs
  • Funder: National Science Foundation (NSF)
  • Project Code: 1117631
  • Funding stream: Directorate for Computer & Information Science & Engineering | Division of Information and Intelligent Systems
Download from

[1] 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]

[2] 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.

[3] M. Chudnovsky, P. Maceli and M. Zhong, Three-coloring graphs with no induced six-edge path I : the triangle-free case, manuscript.

[4] K. Edwards, The complexity of colouring problems on dense graphs, Theoret. Comput. Sci. 43 (1986), 337-343.

[5] 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.

[6] I. Holyer, The NP-completeness of edge coloring, SIAM J. Comput. 10 (1981), 718- 720. [OpenAIRE]

[7] S. Huang, Improved Complexity Results on k-Coloring Pt-Free Graphs, Proc. MFCS 2013, LNCS, to appear.

[8] 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.

[9] R. M. Karp, Reducibility Among Combinatorial Problems, Complexity of Computer Computations, New York: Plenum., 85-103.

[10] 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]

[11] D. Leven and Z. Galil, NP-completeness of finding the chromatic index of regular graphs. J. Algorithm 4 (1983), 35-44. [OpenAIRE]

[12] B. Randerath and I. Schiermeyer, 3-Colorability ∈ P for P6-free graphs, Discrete Appl. Math. 136 (2004), 299-313. [OpenAIRE]

[13] B. Randerath, I. Schiermeyer and M.Tewes, Three-colorability and forbidden subgraphs. II: polynomial algorithms, Discrete Mathematics 251 (2002), 137153. [OpenAIRE]

[14] J. Stacho, private communication.

[15] L. Stockmeyer, Planar 3-colorability is polynomial complete, SIGACT News (1973), 19-25.

Powered by OpenAIRE Research Graph
Any information missing or wrong?Report an Issue