On $3$-Colorable $P_5$-Free Graphs

DOI10.1137/110829222zbMath1261.05030OpenAlexW1969119072MaRDI QIDQ4915195

Frédéric Maffray, Grégory Morel

Publication date: 9 April 2013

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/110829222

zbMATH Keywords

stabilitygraph algorithmstructure theorem\(P_5\)-free graphs

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Structural characterization of families of graphs (05C75) 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 (17)

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 ⋮ $t$-Perfection in $P_5$-Free Graphs ⋮ A refinement on the structure of vertex-critical \((P_5, \mathrm{gem})\)-free graphs ⋮ Infinite families of \(k\)-vertex-critical \((P_5, C_5)\)-free graphs ⋮ 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 ⋮ Better 3-coloring algorithms: excluding a triangle and a seven vertex path ⋮ Critical vertices and edges in \(H\)-free graphs ⋮ \(k\)-critical graphs in \(P_5\)-free graphs ⋮ \(k\)-critical graphs in \(P_5\)-free graphs ⋮ Spectral properties of cographs andP₅-free graphs ⋮ Obstructions for Three-Coloring and List Three-Coloring $H$-Free Graphs

This page was built for publication: On $3$-Colorable $P_5$-Free Graphs