Dichotomizing \(k\)-vertex-critical \(H\)-free graphs for \(H\) of order four
From MaRDI portal
Publication:831869
DOI10.1016/j.dam.2021.11.001zbMath1485.05053OpenAlexW4225363091MaRDI QIDQ831869
Joe Sawada, Ben Cameron, Chính T. Hoàng
Publication date: 24 March 2022
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.dam.2021.11.001
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Ramsey theory (05D10)
Related Items (3)
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 ⋮ Vertex-critical \(( P_3 + \ell P_1 )\)-free and vertex-critical (gem, co-gem)-free graphs
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- On color-critical (\(P_5\),\(\operatorname{co-}P_5\))-free graphs
- Complexity of coloring graphs without paths and cycles
- Paw-free graphs
- Critical graphs with connected complements
- Critical \((P_6, \mathrm{banner})\)-free graphs
- Constructions of \(k\)-critical \(P_5\)-free graphs
- List coloring in the absence of a linear forest
- Obstructions for three-coloring graphs without induced paths on six vertices
- Vertex-critical \((P_5\), banner)-free graphs
- Practical graph isomorphism. II.
- On a property of the class of n-colorable graphs
- Graph Theory and Probability
- The NP-Completeness of Edge-Coloring
- NP completeness of finding the chromatic index of regular graphs
- Reducibility among Combinatorial Problems
- Obstructions for Three-Coloring and List Three-Coloring $H$-Free Graphs
- \(k\)-critical graphs in \(P_5\)-free graphs
This page was built for publication: Dichotomizing \(k\)-vertex-critical \(H\)-free graphs for \(H\) of order four
