A new lower bound on the number of edges in colour-critical graphs and hypergraphs

DOI10.1016/S0095-8956(02)00035-7zbMath1020.05028MaRDI QIDQ1405127

Alexandr V. Kostochka, Michael Stiebitz

Publication date: 25 August 2003

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

zbMATH Keywords

chromatic numberlist coloringcolor-critical hypergraphGallai tree

Mathematics Subject Classification ID

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

Related Items (15)

A better lower bound on average degree of 4-list-critical graphs ⋮ Coloring vertices and faces of locally planar graphs ⋮ ON LOCALLY-BALANCED 2-PARTITIONS OF BIPARTITE GRAPHS ⋮ Generalized DP-colorings of graphs ⋮ On Density of \(\boldsymbol{\mathbb{Z}_3}\) -Flow-Critical Graphs ⋮ On the edge-density of 4-critical graphs ⋮ Generalized hypergraph coloring ⋮ Ore's conjecture on color-critical graphs is almost true ⋮ The edge density of critical digraphs ⋮ A better lower bound on average degree of online \(k\)-list-critical graphs ⋮ On the critical point-arboricity graphs ⋮ A Brooks-type result for sparse critical graphs ⋮ Improved lower bounds on the number of edges in list critical and online list critical graphs ⋮ A list version of Dirac's theorem on the number of edges in colour-critical graphs ⋮ On list critical graphs

Cites Work

• Excess in critical graphs
• On the minimal number of edges in color-critical graphs
• Colour-critical graphs with few edges
• Proof of a conjecture of T. Gallai concerning connectivity properties of colour-critical graphs
• Note on the colouring of graphs
• A Theorem of R. L. Brooks and a Conjecture of H. Hadwiger
• A list version of Dirac's theorem on the number of edges in colour-critical graphs
• The number of edges in critical graphs.
• On Dirac's Generalization of Brooks' Theorem
• On the number of edges in colour-critical graphs and hypergraphs
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: A new lower bound on the number of edges in colour-critical graphs and hypergraphs