Skip to Main content Skip to Navigation
New interface
Preprints, Working Papers, ...

A note on ∆-critical graphs

Abstract : A k-critical graph is a k-chromatic graph whose proper subgraphs are all (k − 1)colourable. An old open problem due to Borodin and Kostochka asserts that for k ≥ 9, no k-critical graph G with k = ∆(G) exists, where ∆(G) denotes the maximum degree of G. We show that if a certain special list-colouring property holds for every 8-critical graph with ∆ = 8 (which is true for the apparently only known example) then the Borodin-Kostochka Conjecture holds. We also briefly survey constructions of ∆-critical graphs with ∆ ≤ 8, highlighting the apparent scarcity of such graphs once ∆ exceeds 6.
Document type :
Preprints, Working Papers, ...
Complete list of metadata
Contributor : Reza Naserasr Connect in order to contact the contributor
Submitted on : Sunday, November 6, 2022 - 12:07:35 AM
Last modification on : Wednesday, November 9, 2022 - 4:09:06 AM


DeltaCritical 15August2022.pdf
Files produced by the author(s)


  • HAL Id : hal-03840737, version 1



Penny Haxell, Reza Naserasr. A note on ∆-critical graphs. 2022. ⟨hal-03840737⟩



Record views


Files downloads