Critical \((P_6, \mathrm{banner})\)-free graphs
From MaRDI portal
Publication:1732108
DOI10.1016/j.dam.2018.11.010zbMath1407.05094OpenAlexW2906676377MaRDI QIDQ1732108
Shenwei Huang, Yongtang Shi, Tao Li
Publication date: 22 March 2019
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.dam.2018.11.010
Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Perfect graphs (05C17)
Related Items (7)
Dichotomizing \(k\)-vertex-critical \(H\)-free graphs for \(H\) of order four ⋮ Vertex-critical \((P_5, \mathrm{chair})\)-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 ⋮ \(k\)-critical graphs in \(P_5\)-free graphs ⋮ \(k\)-critical graphs in \(P_5\)-free graphs
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- 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
- Ore's conjecture on color-critical graphs is almost true
- Improved complexity results on \(k\)-coloring \(P_t\)-free graphs
- The strong perfect graph theorem
- 3-colorability \(\in \mathcal P\) for \(P_{6}\)-free graphs.
- Constructions of \(k\)-critical \(P_5\)-free graphs
- 4-coloring \((P_6, \text{bull})\)-free graphs
- Certifying coloring algorithms for graphs without long induced paths
- Note on the colouring of graphs
- A Certifying Algorithm for 3-Colorability of P 5-Free Graphs
- Obstructions for three-coloring graphs with one forbidden induced subgraph
- Exhaustive generation of k‐critical ‐free graphs
- A Property of 4-Chromatic Graphs and some Remarks on Critical Graphs
- Some Theorems on Abstract Graphs
This page was built for publication: Critical \((P_6, \mathrm{banner})\)-free graphs
