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

DOI10.1016/J.DAM.2021.11.001MaRDI QIDQ831869zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

graph coloringcertifying algorithms

Mathematics Subject Classification ID

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)

Recommendations

• 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
• \(k\)-critical graphs in \(P_5\)-free graphs
• On color-critical (\(P_5\),\(\operatorname{co-}P_5\))-free graphs

Cites work

• scientific article; zbMATH DE number 1118889 (Why is no real title available?)
• Coloring edges and vertices of graphs without short or long cycles
• Complexity of coloring graphs without paths and cycles
• Constructions of k-critical P₅-free graphs
• Critical \((P_6, \mathrm{banner})\)-free graphs
• Critical graphs with connected complements
• Graph Theory and Probability
• List coloring in the absence of a linear forest
• NP completeness of finding the chromatic index of regular graphs
• Obstructions for three-coloring and list three-coloring \(H\)-free graphs
• Obstructions for three-coloring graphs without induced paths on six vertices
• On a property of the class of n-colorable graphs
• On color-critical (\(P_5\),\(\operatorname{co-}P_5\))-free graphs
• Paw-free graphs
• Practical graph isomorphism. II.
• Reducibility among combinatorial problems
• The NP-Completeness of Edge-Coloring
• Vertex-critical \((P_5\), banner)-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
• Critical vertices and edges in \(H\)-free graphs
• A refinement on the structure of vertex-critical \((P_5, \mathrm{gem})\)-free graphs
• Exhaustive Generation of k-Critical $${\mathcal H}$$ -Free Graphs
• Dichotomizing $k$-vertex-critical $H$-free graphs for $H$ of order four
• \(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

Describes a project that uses

Uses Software

• Traces
• nauty

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)