Vertex-critical graphs far from edge-criticality

2023/10/19 by Martinsson, Anders, Steiner, Raphael · 1 citation
#05C15 #05C65 #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2310.12891

Abstract

Let r be any positive integer. We prove that for every sufficiently large k there exists a k-chromatic vertex-critical graph G such that χ(G-R)=k for every set R ⊆ E(G) with |R|≤ r. This partially solves a problem posed by Erdős in 1985, who asked whether the above statement holds for k ≥ 4.

Cited by

• Critical edge sets in vertex-critical graphs

Related

• Critical edge sets in vertex-critical graphs
• Vertex-critical graphs in co-gem-free graphs
• Vertex-critical (P₃+ℓ P₁)-free and vertex-critical (gem, co-gem)-free graphs
• Critical graphs for the chromatic edge-stability number
• Coloring Δ-Critical Graphs With Small High Vertex Cliques