Name
Abstract | ||
|---|---|---|
A (hyper)graph G is called k-critical if it has chromatic number k, but every proper sub(hyper)graph of it is (k-1)-colourable. We prove that for sufficiently large k, every k-critical triangle-free graph on n vertices has at least (k-o(k))n edges. Furthermore, we show that every (k+1)-critical hypergraph on n vertices and without graph edges has at least $(k-3/\sqrt[3]{k}) n$ edges. Both bounds differ from the best possible bounds by o(kn) even for graphs or hypergraphs of arbitrary girth. |
Year | DOI | Venue |
|---|---|---|
2000 | 10.1007/s004930070005 | Combinatorica |
Field | DocType | Volume |
Pseudoforest,Discrete mathematics,Combinatorics,Multigraph,Graph power,Gray graph,Cycle graph,Multiple edges,Mathematics,Path graph,Complement graph | Journal | 20 |
Issue | ISSN | Citations |
4 | 0209-9683 | 9 |
PageRank | References | Authors |
1.20 | 6 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Alexandr V. Kostochka | 1 | 682 | 89.87 |
| Michael Stiebitz | 2 | 207 | 30.08 |