Dichotomizing \(k\)-vertex-critical \(H\)-free graphs for \(H\) of order four

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

zbMATH Keywords

graph coloringcertifying algorithms

Mathematics Subject Classification ID

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

• nauty
• Traces

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