Abstract
A graph G is called k-critical if G is k-chromatic but every proper subgraph of G has chromatic number at most k - 1. In this paper the following result is proved. If G is a k-critical graph (k≥4) on n vertices, then 2|E(G)|>(k-1)n + ((k - 3)/(k2 -3)n + k - 4 where n ≥ k + 2 and n ≠ 2k -1. This improves earlier bounds established by Dirac (1957) and Gallai (1963).
| Original language | English (US) |
|---|---|
| Pages (from-to) | 125-137 |
| Number of pages | 13 |
| Journal | Discrete Mathematics |
| Volume | 191 |
| Issue number | 1-3 |
| DOIs | |
| State | Published - Sep 28 1998 |
| Externally published | Yes |
Keywords
- Chromatic number
- Critical graphs
ASJC Scopus subject areas
- Theoretical Computer Science
- Discrete Mathematics and Combinatorics
Fingerprint
Dive into the research topics of 'Colour-critical graphs with few edges'. Together they form a unique fingerprint.Cite this
- APA
- Standard
- Harvard
- Vancouver
- Author
- BIBTEX
- RIS