Name
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). |
Year | DOI | Venue |
|---|---|---|
2003 | 10.1016/S0095-8956(02)00035-7 | J. Comb. Theory, Ser. B |
Keywords | Field | DocType |
chromatic number k,proper subgraph,k-critical graph,graph g,colour-critical graph,n edge,lower bound | Discrete mathematics,Graph,Combinatorics,Vertex (geometry),Chromatic scale,Upper and lower bounds,Constraint graph,Mathematics | Journal |
Volume | Issue | ISSN |
87 | 2 | Journal of Combinatorial Theory, Series B |
Citations | PageRank | References |
14 | 1.15 | 9 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Alexandr V. Kostochka | 1 | 682 | 89.87 |
| Michael Stiebitz | 2 | 207 | 30.08 |