Deciding k-colorability of P₅-free graphs in polynomial time

DOI10.1007/S00453-008-9197-8zbMATH Open1222.68083OpenAlexW2282776087MaRDI QIDQ848637FDOQ848637

Authors: Chính T. Hoàng, Joe Sawada, Xiao Shu, Marcin Kamiński, Vadim Lozin 

Publication date: 4 March 2010

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-008-9197-8

Recommendations

• A Note on k-Colorability of P 5-Free Graphs
• Two complexity results for the vertex coloring problem
• The complexity of coloring graphs without long induced paths
• Narrowing Down the Gap on the Complexity of Coloring P k -Free Graphs
• 4-coloring \(H\)-free graphs when \(H\) is small

zbMATH Keywords

graph coloringpolynomial-time algorithmdominating clique\(P_5\)-free graph

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cites Work

• On the NP-completeness of the \(k\)-colorability problem for triangle-free graphs
• 3-colorability \(\in \mathcal P\) for \(P_{6}\)-free graphs.
• Title not available (Why is that?)
• The NP-Completeness of Edge-Coloring
• Title not available (Why is that?)
• Title not available (Why is that?)
• Matrix multiplication via arithmetic progressions
• Dominating cliques in \(P_ 5\)-free graphs
• Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph
• Permutation Graphs and Transitive Graphs
• The complexity of coloring graphs without long induced paths
• Three-colourability and forbidden subgraphs. II: Polynomial algorithms
• Vertex colouring and forbidden subgraphs -- a survey
• Weighted parameters in \((P_5,\overline {P_5})\)-free graphs
• On the complexity of 4-coloring graphs without long induced paths
• Optimizing weakly triangulated graphs
• Title not available (Why is that?)
• Coloration de graphes : fondements et applications
• On the hardness of approximating the chromatic number

Cited In (96)

• Colouring of graphs with Ramsey-type forbidden subgraphs
• A New Characterization of P 6-Free Graphs
• On the parameterized complexity of coloring graphs in the absence of a linear forest
• \(H\)-colouring \(P_t\)-free graphs in subexponential time
• Connected vertex cover for \((sP_1+P_5)\)-free graphs
• \(k\)-critical graphs in \(P_5\)-free graphs
• Algorithms and almost tight results for 3-colorability of small diameter graphs
• Coloring graphs without short cycles and long induced paths
• Closing complexity gaps for coloring problems on \(H\)-free graphs
• The vertex colourability problem for \(\{\text{claw}, \text{butterfly}\}\)-free graphs is polynomial-time solvable
• Coloring problems on bipartite graphs of small diameter
• Solving problems on generalized convex graphs via mim-width
• Choosability of P 5-Free Graphs
• On the Complexity of the Vertex 3-Coloring Problem for the Hereditary Graph Classes With Forbidden Subgraphs of Small Size
• Constructions of \(k\)-critical \(P_5\)-free graphs
• Vertex coloring of graphs with few obstructions
• Colouring vertices of triangle-free graphs without forests
• A complete classification of the complexity of the vertex 3-colourability problem for quadruples of induced 5-vertex prohibitions
• Polynomial-time algorithms for minimum weighted colorings of \((P_5, \overline{P}_5)\)-free graphs and similar graph classes
• Title not available (Why is that?)
• Title not available (Why is that?)
• Finding Large $H$-Colorable Subgraphs in Hereditary Graph Classes
• Narrowing Down the Gap on the Complexity of Coloring P k -Free Graphs
• Coloring graphs without short cycles and long induced paths
• Independent feedback vertex set for \(P_5\)-free graphs
• Updating the complexity status of coloring graphs without a fixed induced linear forest
• Colouring H-free graphs of bounded diameter.
• A refinement on the structure of vertex-critical \((P_5, \mathrm{gem})\)-free graphs
• Complexity of \(C_k\)-coloring in hereditary classes of graphs
• Three-coloring and list three-coloring of graphs without induced paths on seven vertices
• 4-coloring \((P_6, \text{bull})\)-free graphs
• Colouring square-free graphs without long induced paths.
• Certifying coloring algorithms for graphs without long induced paths
• Stable sets in \(k\)-colorable \(P_{5}\)-free graphs
• A new characterization of \(P_k\)-free graphs
• On list \(k\)-coloring convex bipartite graphs
• A Note on k-Colorability of P 5-Free Graphs
• Some results on graphs without long induced paths
• Colouring \((P_r + P_s)\)-free graphs
• List 3-coloring \(P_t\)-free graphs with no induced 1-subdivision of \(K_{1 , s}\)
• Independent Feedback Vertex Set for P_5-free Graphs
• List \(k\)-colouring \(P_t\)-free graphs: a mim-width perspective
• List coloring in the absence of a linear forest
• Colouring square-free graphs without long induced paths
• 3-colouring AT-free graphs in polynomial time
• List coloring in the absence of a linear forest
• The complexity of the vertex 3-colorability problem for some hereditary classes defined by 5-vertex forbidden induced subgraphs
• A Survey on the Computational Complexity of Coloring Graphs with Forbidden Subgraphs
• Colouring vertices of triangle-free graphs
• Partitioning Graphs into Connected Parts
• On some domination colorings of graphs
• 4-colorability of \(P_6\)-free graphs
• Data reduction for graph coloring problems
• Colouring (P_r+P_s)-Free Graphs
• Coloring of pseudocubic graphs in three colors
• Complexity of coloring graphs without paths and cycles
• On color-critical (\(P_5\),\(\operatorname{co-}P_5\))-free graphs
• Determining the chromatic number of triangle-free \(2P_3\)-free graphs in polynomial time
• Connected greedy coloring of \(H\)-free graphs
• 4-coloring \(H\)-free graphs when \(H\) is small
• 4‐Coloring P ₆ ‐Free Graphs with No Induced 5‐Cycles
• \(k\)-critical graphs in \(P_5\)-free graphs
• On 3-coloring of \((2P_4,C_5)\)-free graphs
• On 3-coloring of \((2P_4,C_5)\)-free graphs
• Covering minimal separators and potential maximal cliques in \(P_t\)-free graphs
• Improved complexity results on \(k\)-coloring \(P_t\)-free graphs
• Two complexity results for the vertex coloring problem
• Classifying \(k\)-edge colouring for \(H\)-free graphs
• The complexity of coloring graphs without long induced paths
• Two cases of polynomial-time solvability for the coloring problem
• Polynomial cases for the vertex coloring problem
• A certifying algorithm for 3-colorability of \(P _{5}\)-free graphs
• Deciding \(k\)-colorability in expected polynomial time
• Complete complexity dichotomy for $7$-edge forbidden subgraphs in the edge coloring problem
• Better 3-coloring algorithms: excluding a triangle and a seven vertex path
• Approximately coloring graphs without long induced paths
• On algorithmic applications of sim-width and mim-width of \((H_1,H_2)\)-free graphs
• List 3-coloring on comb-convex and caterpillar-convex bipartite graphs
• Complexity Dichotomy for List-5-Coloring with a Forbidden Induced Subgraph
• An intractability result for the vertex 3-colourability problem
• On \(r\)-hued colorings of graphs without short induced paths
• Critical \((P_5,\mathit{dart})\)-free graphs
• Solving problems on generalized convex graphs via mim-width
• Cops and Robbers on \(\boldsymbol{P_5}\)-Free Graphs
• Near optimal colourability on hereditary graph families
• Colouring generalized claw-free graphs and graphs of large girth: bounding the diameter
• A complete complexity dichotomy of the edge-coloring problem for all sets of 8-edge forbidden subgraphs
• List-3-coloring ordered graphs with a forbidden induced subgraphs
• 3-colouring \(P_t\)-free graphs without short odd cycles
• Infinite families of \(k\)-vertex-critical \((P_5, C_5)\)-free graphs
• Four-Coloring \(P_6\)-Free Graphs. I. Extending an Excellent Precoloring
• Four-Coloring \(\boldsymbol{P_6}\)-Free Graphs. II. Finding an Excellent Precoloring
• Fundamentals of Computation Theory
• Vertex-critical \(( P_3 + \ell P_1 )\)-free and vertex-critical (gem, co-gem)-free graphs
• On coloring a class of claw-free and hole-twin-free graphs
• List homomorphism: beyond the known boundaries

This page was built for publication: Deciding \(k\)-colorability of \(P_5\)-free graphs in polynomial time

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q848637)