Deciding $k$-colorability of $P_5$-free graphs in polynomial time

DOI10.1007/s00453-008-9197-8zbMath1222.68083OpenAlexW2282776087MaRDI QIDQ848637

Joe Sawada, Chính T. Hoàng, Xiao Shu, Marcin Kaminski, Vadim V. 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

zbMATH Keywords

graph coloring polynomial-time algorithm dominating clique $P_5$-free graph

Mathematics Subject Classification ID

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

Related Items (84)

The vertex colourability problem for $\{\text{claw}, \text{butterfly}\}$-free graphs is polynomial-time solvable ⋮ 4-Coloring H-Free Graphs When H Is Small ⋮ Coloring problems on bipartite graphs of small diameter ⋮ Solving problems on generalized convex graphs via mim-width ⋮ An intractability result for the vertex 3-colourability problem ⋮ A new characterization of $P_k$-free graphs ⋮ 4-colorability of $P_6$-free graphs ⋮ On color-critical ($P_5$,$\operatorname{co-}P_5$)-free graphs ⋮ Complexity of coloring graphs without paths and cycles ⋮ Vertex coloring of graphs with few obstructions ⋮ On some domination colorings of graphs ⋮ Colouring generalized claw-free graphs and graphs of large girth: bounding the diameter ⋮ 4-coloring $(P_6, \text{bull})$-free graphs ⋮ 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. ⋮ Colouring $(P_r + P_s)$-free graphs ⋮ Certifying coloring algorithms for graphs without long induced paths ⋮ Data reduction for graph coloring problems ⋮ Colouring of graphs with Ramsey-type forbidden subgraphs ⋮ 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 ⋮ 3-colouring AT-free graphs in polynomial time ⋮ On $r$-hued colorings of graphs without short induced paths ⋮ Infinite families of $k$-vertex-critical $(P_5, C_5)$-free graphs ⋮ Four-Coloring $P_6$-Free Graphs. I. Extending an Excellent Precoloring ⋮ A complete classification of the complexity of the vertex 3-colourability problem for quadruples of induced 5-vertex prohibitions ⋮ Determining the chromatic number of triangle-free $2P_3$-free graphs in polynomial time ⋮ Four-Coloring $\boldsymbol{P_6}$-Free Graphs. II. Finding an Excellent Precoloring ⋮ List homomorphism: beyond the known boundaries ⋮ Unnamed Item ⋮ A New Characterization of P 6-Free Graphs ⋮ 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 ⋮ Cops and Robbers on $\boldsymbol{P_5}$-Free Graphs ⋮ Near optimal colourability on hereditary graph families ⋮ 3-colouring $P_t$-free graphs without short odd cycles ⋮ On algorithmic applications of sim-width and mim-width of $(H_1,H_2)$-free graphs ⋮ Coloring graphs without short cycles and long induced paths ⋮ 4‐Coloring P ₆ ‐Free Graphs with No Induced 5‐Cycles ⋮ A Survey on the Computational Complexity of Coloring Graphs with Forbidden Subgraphs ⋮ On the parameterized complexity of coloring graphs in the absence of a linear forest ⋮ Better 3-coloring algorithms: excluding a triangle and a seven vertex path ⋮ Covering minimal separators and potential maximal cliques in $P_t$-free graphs ⋮ Polynomial cases for the vertex coloring problem ⋮ 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 ⋮ Solving problems on generalized convex graphs via mim-width ⋮ Improved complexity results on $k$-coloring $P_t$-free graphs ⋮ Two complexity results for the vertex coloring problem ⋮ Finding Large $H$-Colorable Subgraphs in Hereditary Graph Classes ⋮ Closing complexity gaps for coloring problems on $H$-free graphs ⋮ Constructions of $k$-critical $P_5$-free graphs ⋮ List coloring in the absence of a linear forest ⋮ Unnamed Item ⋮ Approximately coloring graphs without long induced paths ⋮ Narrowing Down the Gap on the Complexity of Coloring P k -Free Graphs ⋮ Colouring Vertices of Triangle-Free Graphs ⋮ Three-coloring and list three-coloring of graphs without induced paths on seven vertices ⋮ Connected vertex cover for $(sP_1+P_5)$-free graphs ⋮ Coloring of pseudocubic graphs in three colors ⋮ Two cases of polynomial-time solvability for the coloring problem ⋮ $k$-critical graphs in $P_5$-free graphs ⋮ On 3-coloring of $(2P_4,C_5)$-free graphs ⋮ $k$-critical graphs in $P_5$-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 ⋮ Coloring Graphs without Short Cycles and Long Induced Paths ⋮ On list $k$-coloring convex bipartite graphs ⋮ Partitioning Graphs into Connected Parts ⋮ Colouring (P_r+P_s)-Free Graphs ⋮ Colouring H-free graphs of bounded diameter. ⋮ Updating the complexity status of coloring graphs without a fixed induced linear forest ⋮ Colouring vertices of triangle-free graphs without forests ⋮ List Coloring in the Absence of a Linear Forest ⋮ $H$-colouring $P_t$-free graphs in subexponential time ⋮ Colouring square-free graphs without long induced paths ⋮ Connected greedy coloring of $H$-free graphs ⋮ On coloring a class of claw-free and hole-twin-free graphs ⋮ Polynomial-time algorithms for minimum weighted colorings of $(P_5, \overline{P}_5)$-free graphs and similar graph classes ⋮ Independent Feedback Vertex Set for P_5-free Graphs ⋮ Algorithms and almost tight results for 3-colorability of small diameter graphs

Cites Work

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

Deciding \(k\)-colorability of \(P_5\)-free graphs in polynomial time