English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

A graph is called $k$-critical if its chromatic number is $k$ but any propersubgraph has chromatic number less than $k$. An old and important problem ingraph theory asks to determine the maximum number of edges in an $n$-vertex$k$-critical graph. This is widely open for any integer $k\geq 4$. Using astructural characterization of Greenwell and Lov\'asz and an extremal result ofSimonovits, Stiebitz proved in 1987 that for $k\geq 4$ and sufficiently large$n$, this maximum number is less than the number of edges in the $n$-vertexbalanced complete $(k-2)$-partite graph. In this paper we obtain the firstimprovement on the above result in the past 35 years. Our proofs combinearguments from extremal graph theory as well as some structural analysis. A keylemma we use indicates a partial structure in dense $k$-critical graphs, whichmay be of independent interest.

On the maximum number of edges in k-critical graphs