A lower bound on the number of edges in DP-critical graphs. II. Four colors

2024/10/02 by Peter Bradshaw, Ilkyoo Choi, Bradshaw, Peter +5
Computer Science · Mathematics · #05C07 #05C15 #05C35 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory

paper · pdf · doi:10.48550/arxiv.2410.01191

openalex publication_date 2024/10/02 · openalex created_date 2024/10/30 · openalex updated_date 2026/07/28

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')(3 + (1)/(5) ) (n)/(2). This is the first bound on f_DP(n,4) that is asymptotically better than the well-known bound f(n,4)≥ (3 + (1)/(13) ) (n)/(2) by Gallai from 1963. The result also yields a better bound on f_ℓ(n,4) than the one known before.

Related

• A lower bound on the number of edges in DP-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
• On critical graphs for the chromatic edge-stability number