## Abstract

A graph G is k-critical if it has chromatic number k, but every proper subgraph of G is (k-1)-colorable. Let f_{k}(n) denote the minimum number of edges in an n-vertex k-critical graph. We give a lower bound, f_{k}(n)≥F(k, n), that is sharp for every n=1(modk-1). The bound is also sharp for k=4 and every n≥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 f_{k}(n) for every fixed k. It also proves that the conjecture by Ore from 1967 that for every k≥4 and n≥k+2, fk(n+k-1)=fk(n)+k-12(k-2k-1) holds for each k≥4 for all but at most k^{3}/12 values of n. We give a polynomial-time algorithm for (k-1)-coloring of a graph G that satisfies |E(G[W])|<F(k, |W|) for all W⊆V(G), |W|≥k. We also present some applications of the result.

Original language | English (US) |
---|---|

Pages (from-to) | 73-101 |

Number of pages | 29 |

Journal | Journal of Combinatorial Theory. Series B |

Volume | 109 |

DOIs | |

State | Published - Nov 1 2014 |

## Keywords

- Graph coloring
- K-critical graphs
- Sparse graphs

## ASJC Scopus subject areas

- Theoretical Computer Science
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics