Skip to main navigation Skip to search Skip to main content

Colour-critical graphs with few edges

Research output: Contribution to journal › Article › peer-review

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 languageEnglish (US)
Pages (from-to)125-137
Number of pages13
JournalDiscrete Mathematics
Volume191
Issue number1-3
DOIs
StatePublished - Sep 28 1998
Externally publishedYes

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