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

O. V. Borodin; A. V. Kostochka

doi:10.1016/0095-8956(77)90037-5

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

Research output: Contribution to journal › Article › peer-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 language	English (US)
Pages (from-to)	247-250
Number of pages	4
Journal	Journal of Combinatorial Theory, Series B
Volume	23
Issue number	2-3
DOIs	https://doi.org/10.1016/0095-8956(77)90037-5
State	Published - 1977
Externally published	Yes

ASJC Scopus subject areas

Theoretical Computer Science
Discrete Mathematics and Combinatorics
Computational Theory and Mathematics

Online availability

10.1016/0095-8956(77)90037-5

Library availability

Discover UIUC Full Text

Cite this

@article{f436cb0ff34f486490e2b2fb06c37f0d,

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

abstract = "Gr{\"u}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.",

author = "Borodin, {O. V.} and Kostochka, {A. V.}",

year = "1977",

doi = "10.1016/0095-8956(77)90037-5",

language = "English (US)",

volume = "23",

pages = "247--250",

journal = "Journal of Combinatorial Theory, Series B",

issn = "0095-8956",

publisher = "Academic Press Inc.",

number = "2-3",

}

TY - JOUR

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

AU - Borodin, O. V.

AU - Kostochka, A. V.

PY - 1977

Y1 - 1977

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0003490401&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0003490401&partnerID=8YFLogxK

U2 - 10.1016/0095-8956(77)90037-5

DO - 10.1016/0095-8956(77)90037-5

M3 - Article

AN - SCOPUS:0003490401

SN - 0095-8956

VL - 23

SP - 247

EP - 250

JO - Journal of Combinatorial Theory, Series B

JF - Journal of Combinatorial Theory, Series B

IS - 2-3

ER -

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

Abstract

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this