Three-coloring and list three-coloring of graphs without induced paths on seven vertices

DOI10.1007/s00493-017-3553-8zbMath1413.05101OpenAlexW2617354712MaRDI QIDQ1786047

Oliver Schaudt, Maria Chudnovsky, Mingxian Zhong, Peter Maceli, Flavia Bonomo-Braberman, Maya Jakobine Stein

Publication date: 24 September 2018

Published in: Combinatorica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00493-017-3553-8

zbMATH Keywords

complexitycoloringlist coloring\(H\)-free graphs

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items

The vertex colourability problem for \(\{\text{claw}, \text{butterfly}\}\)-free graphs is polynomial-time solvable, An intractability result for the vertex 3-colourability problem, Colouring generalized claw-free graphs and graphs of large girth: bounding the diameter, The complexity of the vertex 3-colorability problem for some hereditary classes defined by 5-vertex forbidden induced subgraphs, Complete complexity dichotomy for $7$-edge forbidden subgraphs in the edge coloring problem, Colouring square-free graphs without long induced paths., New formulations and branch-and-cut procedures for the longest induced path problem, Colouring \((P_r + P_s)\)-free graphs, Certifying coloring algorithms for graphs without long induced paths, Vertex coloring of a graph for memory constrained scenarios, Complexity Dichotomy for List-5-Coloring with a Forbidden Induced Subgraph, A refinement on the structure of vertex-critical \((P_5, \mathrm{gem})\)-free graphs, Complexity of \(C_k\)-coloring in hereditary classes of graphs, MIP formulations for induced graph optimization problems: a tutorial, Infinite families of \(k\)-vertex-critical \((P_5, C_5)\)-free graphs, Four-Coloring \(P_6\)-Free Graphs. I. Extending an Excellent Precoloring, 3-coloring \(C_4\) or \(C_3\)-free diameter two graphs, A complete classification of the complexity of the vertex 3-colourability problem for quadruples of induced 5-vertex prohibitions, Four-Coloring \(\boldsymbol{P_6}\)-Free Graphs. II. Finding an Excellent Precoloring, Unnamed Item, List 3-coloring \(P_t\)-free graphs with no induced 1-subdivision of \(K_{1 , s}\), Vertex-critical \(( P_3 + \ell P_1 )\)-free and vertex-critical (gem, co-gem)-free graphs, 3-colouring \(P_t\)-free graphs without short odd cycles, 4‐Coloring P ₆ ‐Free Graphs with No Induced 5‐Cycles, A Survey on the Computational Complexity of Coloring Graphs with Forbidden Subgraphs, Better 3-coloring algorithms: excluding a triangle and a seven vertex path, Structural domination and coloring of some \(( P_7 , C_7)\)-free graphs, List 3-coloring graphs with no induced \(P_6 + rP_3\), Covering minimal separators and potential maximal cliques in \(P_t\)-free graphs, List \(k\)-colouring \(P_t\)-free graphs: a mim-width perspective, Independent feedback vertex set for \(P_5\)-free graphs, Classifying \(k\)-edge colouring for \(H\)-free graphs, 3-Colorable Subclasses of $P_8$-Free Graphs, Finding Large $H$-Colorable Subgraphs in Hereditary Graph Classes, Unnamed Item, Approximately coloring graphs without long induced paths, Obstructions for three-coloring graphs without induced paths on six vertices, Coloring of pseudocubic graphs in three colors, \(k\)-critical graphs in \(P_5\)-free graphs, Colouring graphs of bounded diameter in the absence of small cycles, On 3-coloring of \((2P_4,C_5)\)-free graphs, \(k\)-critical graphs in \(P_5\)-free graphs, Colouring graphs of bounded diameter in the absence of small cycles, Obstructions for Three-Coloring and List Three-Coloring $H$-Free Graphs, On 3-coloring of \((2P_4,C_5)\)-free graphs, On the Complexity of the Vertex 3-Coloring Problem for the Hereditary Graph Classes With Forbidden Subgraphs of Small Size, On list \(k\)-coloring convex bipartite graphs, Colouring (P_r+P_s)-Free Graphs, Colouring H-free graphs of bounded diameter., Colouring square-free graphs without long induced paths, On coloring a class of claw-free and hole-twin-free graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Deciding \(k\)-colorability of \(P_5\)-free graphs in polynomial time
• Matrix multiplication via arithmetic progressions
• The complexity of colouring problems on dense graphs
• A linear-time algorithm for testing the truth of certain quantified Boolean formulas
• On the NP-completeness of the \(k\)-colorability problem for triangle-free graphs
• 3-colorability \(\in \mathcal P\) for \(P_{6}\)-free graphs.
• Three-colourability and forbidden subgraphs. II: Polynomial algorithms
• Closing complexity gaps for coloring problems on \(H\)-free graphs
• Improved Complexity Results on k-Coloring P t -Free Graphs
• A New Characterization of $$P_k$$-free Graphs
• 4‐Coloring P ₆ ‐Free Graphs with No Induced 5‐Cycles
• A Survey on the Computational Complexity of Coloring Graphs with Forbidden Subgraphs
• The NP-Completeness of Edge-Coloring
• Graph colorings with local constraints -- a survey
• NP completeness of finding the chromatic index of regular graphs
• Narrowing the Complexity Gap for Colouring (C s ,P t )-Free Graphs