A Certifying Algorithm for 3-Colorability of P 5-Free Graphs
From MaRDI portal
Publication:3652246
DOI10.1007/978-3-642-10631-6_61zbMath1272.05191OpenAlexW1866795302MaRDI QIDQ3652246
Joe Sawada, Daniel Bruce, Chính T. Hoàng
Publication date: 17 December 2009
Published in: Algorithms and Computation (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-642-10631-6_61
Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Related Items (29)
On a Verification Framework for Certifying Distributed Algorithms: Distributed Checking and Consistency ⋮ 4-Coloring H-Free Graphs When H Is Small ⋮ Exhaustive Generation of k-Critical $${\mathcal H}$$ -Free Graphs ⋮ On color-critical (\(P_5\),\(\operatorname{co-}P_5\))-free graphs ⋮ Complexity of coloring graphs without paths and cycles ⋮ 4-coloring \((P_6, \text{bull})\)-free graphs ⋮ Certifying coloring algorithms for graphs without long induced paths ⋮ Data reduction for graph coloring problems ⋮ $t$-Perfection in $P_5$-Free Graphs ⋮ A refinement on the structure of vertex-critical \((P_5, \mathrm{gem})\)-free graphs ⋮ Determining the chromatic number of triangle-free \(2P_3\)-free graphs in polynomial time ⋮ Critical (\(P_5\), bull)-free graphs ⋮ Some results on \(k\)-critical \(P_5\)-free graphs ⋮ Vertex-critical \(( P_3 + \ell P_1 )\)-free and vertex-critical (gem, co-gem)-free graphs ⋮ 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 ⋮ Critical vertices and edges in \(H\)-free graphs ⋮ Critical \((P_6, \mathrm{banner})\)-free graphs ⋮ 3-Colorable Subclasses of $P_8$-Free Graphs ⋮ Constructions of \(k\)-critical \(P_5\)-free graphs ⋮ List coloring in the absence of a linear forest ⋮ Narrowing Down the Gap on the Complexity of Coloring P k -Free Graphs ⋮ Obstructions for three-coloring graphs without induced paths on six vertices ⋮ \(k\)-critical graphs in \(P_5\)-free graphs ⋮ \(k\)-critical graphs in \(P_5\)-free graphs ⋮ Obstructions for Three-Coloring and List Three-Coloring $H$-Free Graphs ⋮ Updating the complexity status of coloring graphs without a fixed induced linear forest ⋮ List Coloring in the Absence of a Linear Forest
This page was built for publication: A Certifying Algorithm for 3-Colorability of P 5-Free Graphs
