A certifying algorithm for 3-colorability of P _5-free graphs

DOI10.1007/978-3-642-10631-6_61MaRDI QIDQ3652246zbMATH OpenOpenAlexFDO

Authors Daniel Bruce, Joe Sawada, 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

3-colorabilty $P_5$-free graph algorithm

Coloring of graphs and hypergraphs (05C15) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph algorithms (graph-theoretic aspects) (05C85)

Recommendations

A Note on k-Colorability of P 5-Free Graphs
On 3-colorable P₅-free graphs
On color-critical ($P_5$,$\operatorname{co-}P_5$)-free graphs
Deciding $k$-colorability of $P_5$-free graphs in polynomial time
Obstructions for three-coloring graphs with one forbidden induced subgraph

Cited in

(41)

Critical vertices and edges in $H$-free graphs
Critical $(P_6, \mathrm{banner})$-free graphs
Better 3-coloring algorithms: excluding a triangle and a seven vertex path
Constructions of k-critical P₅-free graphs
List coloring in the absence of a linear forest
Obstructions for three-coloring graphs without induced paths on six vertices
4-coloring $(P_6, \text{bull})$-free graphs
Certifying coloring algorithms for graphs without long induced paths
4-coloring $H$-free graphs when $H$ is small
A survey on the computational complexity of coloring graphs with forbidden subgraphs
Narrowing Down the Gap on the Complexity of Coloring P k -Free Graphs
List coloring in the absence of a linear forest
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
A Note on k-Colorability of P 5-Free Graphs
Data reduction for graph coloring problems
Determining the chromatic number of triangle-free 2P₃-free graphs in polynomial time
On the parameterized complexity of coloring graphs in the absence of a linear forest
3-colorable subclasses of $P_8$-free graphs
On 3-colorable P₅-free graphs
Obstructions for three-coloring and list three-coloring H-free graphs
$t$-perfection in $P_5$-free graphs
On a Verification Framework for Certifying Distributed Algorithms: Distributed Checking and Consistency
$k$-critical graphs in $P_5$-free graphs
k-critical graphs in P₅-free graphs
A refinement on the structure of vertex-critical $(P_5, \mathrm{gem})$-free graphs
Critical ($P_5$, bull)-free graphs
Some results on $k$-critical $P_5$-free graphs
Vertex-critical ( P₃ + P₁ )-free and vertex-critical (gem, co-gem)-free graphs
Critical $(P_5,\mathit{dart})$-free graphs
Certifying induced subgraphs in large graphs
Vertex-critical (P₅,W₄)-free graphs
Some results on critical (P₅, H)-free graphs
Some results on critical (P₅,H)-free graphs
On the finiteness of k-vertex-critical 2P₂-free graphs with forbidden induced squids or bulls
Critical $( P_5 , \mathrm{dart} )$-free graphs
Vertex-critical (P₅, W₄)-free graphs
Minimal obstructions to C₅-Coloring in hereditary graph classes
Minimal obstructions to C₅-coloring in hereditary graph classes
Updating the complexity status of coloring graphs without a fixed induced linear forest

This page was built for publication: A certifying algorithm for 3-colorability of $P _{5}$-free graphs

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