On constructive methods in the theory of colour-critical graphs

DOI10.1016/0012-365X(89)90210-0zbMath0675.05028MaRDI QIDQ1121899

Horst Sachs, Michael Stiebitz

Publication date: 1989

Published in: Discrete Mathematics (Search for Journal in Brave)

zbMATH Keywords

chromatic numberk-critical

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Coloring of graphs and hypergraphs (05C15)

Related Items (13)

On extensions of a conjecture of Gallai ⋮ Some remarks on \((k-1)\)-critical subgraphs of \(k\)-critical graphs ⋮ Questions on color-critical subgraphs ⋮ Edge-critical subgraphs of Schrijver graphs. II: The general case ⋮ Problems and results in extremal combinatorics. I. ⋮ Embedding Graphs into Larger Graphs: Results, Methods, and Problems ⋮ Small odd cycles in 4-chromatic graphs ⋮ On a conjecture of Gallai concerning complete subgraphs of \(k\)-critical graphs ⋮ Critically paintable, choosable or colorable graphs ⋮ On the minimal number of edges in color-critical graphs ⋮ On graphs with strongly independent color-classes ⋮ Generalised Mycielski graphs and the Borsuk-Ulam theorem ⋮ 4-chromatic graphs with large odd girth

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Kneser's conjecture, chromatic number, and homotopy
• On critical subgraphs of colour-critical graphs
• On coloring graphs with locally small chromatic number
• On color critical graphs
• Note to a problem of T. Gallai and G. A. Dirac
• \(K_ 5\) is the only double-critical 5-chromatic graph
• Subgraphs of colour-critical graphs
• Excess in critical graphs
• Three short proofs in graph theory
• On colorings of graphs without short cycles
• The dichromatic number of a digraph
• Proof of a conjecture of T. Gallai concerning connectivity properties of colour-critical graphs
• Colour-critical graphs and hypergraphs
• Circuits in critical graphs
• Map Colour Theorems Related To the Heawood Colour Formula
• A Theorem of R. L. Brooks and a Conjecture of H. Hadwiger
• Map Colour Theorems Related to the Heawood Colour Formula (II)
• Maximal Circuits in Critical Graphs
• 4‐chrome Graphen und vollständige 4‐Graphen
• Construction of Colour-Critical Graphs With Given Major-Vertex Subgraph
• Applications of product colouring
• The number of edges in critical graphs.
• On the Girth of Graphs Critical with Respect to Edge-Colourings
• An Investigation of Colour-Critical Graphs with Complements of Low Connectivity
• On the structure of 5- and 6-chromatic abstract graphs.
• Sur les Ensembles de Sommets Indépendants Dans les Graphes Chromatiques Minimaux
• A Property of 4-Chromatic Graphs and some Remarks on Critical Graphs
• Some Theorems on Abstract Graphs
• The structure of k-chromatic graphs
• Theorems Related To the Four Colour Conjecture
• Paths and Circuits in Critical Graphs
• Sur le coloriage des graphs

This page was built for publication: On constructive methods in the theory of colour-critical graphs