Dichotomizing \(k\)-vertex-critical \(H\)-free graphs for \(H\) of order four
type: Item
instance of: scholarly article
title: Dichotomizing \(k\)-vertex-critical \(H\)-free graphs for \(H\) of order four
zbMATH Open document ID: 1485.05053
author: Ben Cameron
author: Chính T. Hoàng
author: Joe Sawada
published in: Discrete Applied Mathematics
publication date: 2022-03-24T00:00:00Z
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 05D10
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 7497780
zbMATH Keywords: graph coloring
zbMATH Keywords: certifying algorithms
describes a project that uses: nauty
describes a project that uses: Traces
MaRDI profile type: Publication
full work available at URL: j.dam.2021.11.001
OpenAlex ID: W4225363091
cites work: Vertex-critical \((P_5\), banner)-free graphs
cites work: \(k\)-critical graphs in \(P_5\)-free graphs
cites work: Obstructions for Three-Coloring and List Three-Coloring $H$-Free Graphs
cites work: Obstructions for three-coloring graphs without induced paths on six vertices
cites work: List coloring in the absence of a linear forest
cites work: On color-critical (\(P_5\),\(\operatorname{co-}P_5\))-free graphs
cites work: Graph Theory and Probability
cites work: Complexity of coloring graphs without paths and cycles
cites work: Constructions of \(k\)-critical \(P_5\)-free graphs
cites work: The NP-Completeness of Edge-Coloring
cites work: Critical \((P_6, \mathrm{banner})\)-free graphs
cites work: Q3558598
cites work: Reducibility among Combinatorial Problems
cites work: NP completeness of finding the chromatic index of regular graphs
cites work: Practical graph isomorphism. II.
cites work: Paw-free graphs
cites work: On a property of the class of n-colorable graphs
cites work: Critical graphs with connected complements
cites work: Q4376970
DOI: 10.1016/J.DAM.2021.11.001
description: scientific article; zbMATH DE number 7497780