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

Alexandr V. Kostochka; Michael Stiebitz

doi:10.1016/S0095-8956(02)00035-7

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

Alexandr V. Kostochka, Michael Stiebitz

Mathematics

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

Abstract

A graph G is called k-critical if it has chromatic number k, but every proper subgraph of G is (k - 1)-colourable. We prove that every k-critical graph (k ≥ 6) on n ≥ k + 2 vertices has at least 1/2 (k - 1 + k - 3/(k - c)(k - 1) + k - 3) n edges where c = (k - 5) (1/2 - 1/(k - 1)(k - 2)). This improves earlier bounds established by Gallai (Acad. Sci. 8 (1963) 165) and by Krivelevich (Combinatorica 17 (1999) 401).

Original language	English (US)
Pages (from-to)	374-402
Number of pages	29
Journal	Journal of Combinatorial Theory. Series B
Volume	87
Issue number	2
DOIs	https://doi.org/10.1016/S0095-8956(02)00035-7
State	Published - Mar 2003

ASJC Scopus subject areas

Theoretical Computer Science
Discrete Mathematics and Combinatorics
Computational Theory and Mathematics

Online availability

10.1016/S0095-8956(02)00035-7

Library availability

Discover UIUC Full Text

Cite this

@article{9fe98983f7b84a39bbe65d5ad5477098,

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

abstract = "A graph G is called k-critical if it has chromatic number k, but every proper subgraph of G is (k - 1)-colourable. We prove that every k-critical graph (k ≥ 6) on n ≥ k + 2 vertices has at least 1/2 (k - 1 + k - 3/(k - c)(k - 1) + k - 3) n edges where c = (k - 5) (1/2 - 1/(k - 1)(k - 2)). This improves earlier bounds established by Gallai (Acad. Sci. 8 (1963) 165) and by Krivelevich (Combinatorica 17 (1999) 401).",

author = "Kostochka, {Alexandr V.} and Michael Stiebitz",

year = "2003",

month = mar,

doi = "10.1016/S0095-8956(02)00035-7",

language = "English (US)",

volume = "87",

pages = "374--402",

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

issn = "0095-8956",

publisher = "Academic Press Inc.",

number = "2",

}

TY - JOUR

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

AU - Kostochka, Alexandr V.

AU - Stiebitz, Michael

PY - 2003/3

Y1 - 2003/3

N2 - A graph G is called k-critical if it has chromatic number k, but every proper subgraph of G is (k - 1)-colourable. We prove that every k-critical graph (k ≥ 6) on n ≥ k + 2 vertices has at least 1/2 (k - 1 + k - 3/(k - c)(k - 1) + k - 3) n edges where c = (k - 5) (1/2 - 1/(k - 1)(k - 2)). This improves earlier bounds established by Gallai (Acad. Sci. 8 (1963) 165) and by Krivelevich (Combinatorica 17 (1999) 401).

AB - A graph G is called k-critical if it has chromatic number k, but every proper subgraph of G is (k - 1)-colourable. We prove that every k-critical graph (k ≥ 6) on n ≥ k + 2 vertices has at least 1/2 (k - 1 + k - 3/(k - c)(k - 1) + k - 3) n edges where c = (k - 5) (1/2 - 1/(k - 1)(k - 2)). This improves earlier bounds established by Gallai (Acad. Sci. 8 (1963) 165) and by Krivelevich (Combinatorica 17 (1999) 401).

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

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

U2 - 10.1016/S0095-8956(02)00035-7

DO - 10.1016/S0095-8956(02)00035-7

M3 - Article

AN - SCOPUS:0037374173

SN - 0095-8956

VL - 87

SP - 374

EP - 402

JO - Journal of Combinatorial Theory. Series B

JF - Journal of Combinatorial Theory. Series B

IS - 2

ER -

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

Abstract

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this