A lower bound on the number of edges in DP-critical graphs

2024/09/02 by Peter Bradshaw, Ilkyoo Choi, Bradshaw, Peter +5
Computer Science · Mathematics · #Advanced Graph Theory Research #Limits and Structures in Graph Theory #Graph Labeling and Dimension Problems

paper · pdf · doi:10.48550/arxiv.2409.00937

Abstract

A graph G is k-critical (list k-critical, DP k-critical) if χ(G)= k (χ_ℓ(G)= k, χ_DP(G)= k) and for every proper subgraph G' of G, χ(G')(k - 1 + \lceil (k² - 7)/(2k-7) \rceil^-1)(n)/(2). This is the first bound on f_DP(n,k) that is asymptotically better than the well-known bound on f(n,k) by Gallai from 1963. The result also yields a slightly better bound on f_ℓ(n,k) than the ones known before.

Related

• A lower bound on the number of edges in DP-critical graphs. II. Four colors
• Improved lower bounds on the number of edges in list critical and online list critical graphs
• On the maximum number of edges in k-critical graphs
• Sparse critical graphs for defective DP-colorings
• Critical edge sets in vertex-critical graphs