Dichotomizing k-vertex-critical H-free graphs for H of order four
DOI10.1016/J.DAM.2021.11.001zbMATH Open1485.05053OpenAlexW4225363091MaRDI QIDQ831869FDOQ831869
Authors: Ben Cameron, Chính T. Hoàng, Joe Sawada 
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
Recommendations
Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Ramsey theory (05D10)
Cites Work
- Practical graph isomorphism. II.
- Reducibility among combinatorial problems
- Graph Theory and Probability
- Title not available (Why is that?)
- The NP-Completeness of Edge-Coloring
- Critical \((P_6, \mathrm{banner})\)-free graphs
- Paw-free graphs
- NP completeness of finding the chromatic index of regular graphs
- Coloring edges and vertices of graphs without short or long cycles
- Constructions of \(k\)-critical \(P_5\)-free graphs
- On color-critical (\(P_5\),\(\operatorname{co-}P_5\))-free graphs
- Complexity of coloring graphs without paths and cycles
- On a property of the class of n-colorable graphs
- Critical graphs with connected complements
- 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
- Obstructions for three-coloring and list three-coloring \(H\)-free graphs
- \(k\)-critical graphs in \(P_5\)-free graphs
Cited In (10)
- \(k\)-critical graphs in \(P_5\)-free graphs
- Exhaustive generation of \(k\)-critical \(\mathcal{H}\)-free graphs
- Dichotomizing $k$-vertex-critical $H$-free graphs for $H$ of order four
- A refinement on the structure of vertex-critical \((P_5, \mathrm{gem})\)-free graphs
- Critical vertices and edges in \(H\)-free graphs
- Exhaustive Generation of k-Critical $${\mathcal H}$$ -Free Graphs
- \(k\)-critical graphs in \(P_5\)-free graphs
- Some results on \(k\)-critical \(P_5\)-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
This page was built for publication: Dichotomizing \(k\)-vertex-critical \(H\)-free graphs for \(H\) of order four
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q831869)
