On the maximum number of edges in k-critical graphs

• DOI: 10.48550/arxiv.2301.01656
• Publication Date: 2023-01-01
• Authors: Cong Luo; Jie Ma; Tianchi Yang
• Keywords: FOS: Mathematics; Mathematics - Combinatorics; 0102 computer and information sciences; Combinatorics (math.CO); 01 natural sciences

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