Proof of a conjecture of T. Gallai concerning connectivity properties of colour-critical graphs

DOI10.1007/BF02579239zbMath0512.05029WikidataQ123155925 ScholiaQ123155925MaRDI QIDQ1839257

Michael Stiebitz

Publication date: 1982

Published in: Combinatorica (Search for Journal in Brave)

zbMATH Keywords

number of connected componentscritical k-chromatic graphsminor-vertices

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Connectivity (05C40)

Related Items (10)

Path partition number in tough graphs ⋮ On constructive methods in the theory of colour-critical graphs ⋮ Graphs with chromatic number close to maximum degree ⋮ On the edge-density of 4-critical graphs ⋮ Various bounds on the minimum number of arcs in a \(k\)-dicritical digraph ⋮ A new lower bound on the number of edges in colour-critical graphs and hypergraphs ⋮ Ore's conjecture on color-critical graphs is almost true ⋮ Ore-type versions of Brooks' theorem ⋮ On the minimal number of edges in color-critical graphs ⋮ On list critical graphs

Cites Work

• Construction of Colour-Critical Graphs With Given Major-Vertex Subgraph

This page was built for publication: Proof of a conjecture of T. Gallai concerning connectivity properties of colour-critical graphs