Science-advisor
REGISTER info/FAQ
Login
username
password
     
forgot password?
register here
 
Research articles
  search articles
  reviews guidelines
  reviews
  articles index
My Pages
my alerts
  my messages
  my reviews
  my favorites
 
 
Stat
Members: 3667
Articles: 2'599'751
Articles rated: 2609

08 February 2025
 
  » arxiv » 2301.01656

 Article overview



On the maximum number of edges in k-critical graphs
Cong Luo ; Jie Ma ; Tianchi Yang ;
Date 4 Jan 2023
AbstractA 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   
 
Visitor rating: did you like this article? no 1   2   3   4   5   yes

No review found.
 Did you like this article?

This article or document is ...
important:
of broad interest:
readable:
new:
correct:
Global appreciation:

  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.






ScienXe.org
» my Online CV
» Free

home  |  contact  |  terms of use  |  sitemap
Copyright © 2005-2025 - Scimetrica