On an upper bound of a graph's chromatic number, depending on the graph's degree and density

O. V. Borodin, A. V. Kostochka

Research output: Contribution to journalArticlepeer-review

Abstract

Grünbaum's conjecture on the existence of k-chromatic graphs of degree k and girth g for every k ≥ 3, g ≥ 3 is disproved. In particular, the bound obtained states that the chromatic number of a triangle-free graph does not exceed [ 3(σ + 2) 4], where σ is the graph's degree.

Original languageEnglish (US)
Pages (from-to)247-250
Number of pages4
JournalJournal of Combinatorial Theory, Series B
Volume23
Issue number2-3
DOIs
StatePublished - 1977
Externally publishedYes

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics

Fingerprint Dive into the research topics of 'On an upper bound of a graph's chromatic number, depending on the graph's degree and density'. Together they form a unique fingerprint.

Cite this