| | |
| | |
Stat |
Members: 3667 Articles: 2'599'751 Articles rated: 2609
08 February 2025 |
|
| | | |
|
Article overview
| |
|
On the maximum number of edges in k-critical graphs | Cong Luo
; Jie Ma
; Tianchi Yang
; | Date: |
4 Jan 2023 | Abstract: | A graph is called $k$-critical if its chromatic number is $k$ but any proper
subgraph has chromatic number less than $k$. An old and important problem in
graph theory asks to determine the maximum number of edges in an $n$-vertex
$k$-critical graph. This is widely open for any integer $kgeq 4$. Using a
structural characterization of Greenwell and Lov’asz and an extremal result of
Simonovits, Stiebitz proved in 1987 that for $kgeq 4$ and sufficiently large
$n$, this maximum number is less than the number of edges in the $n$-vertex
balanced complete $(k-2)$-partite graph. In this paper we obtain the first
improvement on the above result in the past 35 years. Our proofs combine
arguments from extremal graph theory as well as some structural analysis. A key
lemma we use indicates a partial structure in dense $k$-critical graphs, which
may be of independent interest. | Source: | arXiv, 2301.01656 | Services: | Forum | Review | PDF | Favorites |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
|
| |
|
|
|