کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4656827 | 1632984 | 2014 | 29 صفحه PDF | دانلود رایگان |
A graph G is k-critical if it has chromatic number k, but every proper subgraph of G is (k−1)(k−1)-colorable. Let fk(n)fk(n) denote the minimum number of edges in an n-vertex k -critical graph. We give a lower bound, fk(n)≥F(k,n)fk(n)≥F(k,n), that is sharp for every n=1(modk−1). The bound is also sharp for k=4k=4 and every n≥6n≥6. The result improves a bound by Gallai and subsequent bounds by Krivelevich and Kostochka and Stiebitz, and settles the corresponding conjecture by Gallai from 1963. It establishes the asymptotics of fk(n)fk(n) for every fixed k . It also proves that the conjecture by Ore from 1967 that for every k≥4k≥4 and n≥k+2n≥k+2, fk(n+k−1)=fk(n)+k−12(k−2k−1) holds for each k≥4k≥4 for all but at most k3/12k3/12 values of n . We give a polynomial-time algorithm for (k−1)(k−1)-coloring of a graph G that satisfies |E(G[W])|
Journal: Journal of Combinatorial Theory, Series B - Volume 109, November 2014, Pages 73–101