Vertex-critical graphs far from edge-criticality
OPEN ACCESS
Loading...
Author / Producer
Date
2025-01
Publication Type
Journal Article
ETH Bibliography
yes
Citations
Altmetric
OPEN ACCESS
Data
Rights / License
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 $\chi (G-R)=k$ for every set $R \subseteq E(G)$ with $|R|\le r$ . This partially solves a problem posed by Erd & odblac;s in 1985, who asked whether the above statement holds for $k \ge 4$ .
Permanent link
Publication status
published
External links
Editor
Book title
Journal / series
Volume
34 (1)
Pages / Article No.
151 - 157
Publisher
Cambridge University Press
Event
Edition / version
Methods
Software
Geographic location
Date collected
Date created
Subject
Chromatic number; colour-critical graphs; hypergraphs; probabilistic method
Organisational unit
03993 - Sudakov, Benjamin / Sudakov, Benjamin
02502 - Institut für Operations Research / Institute for Operations Research
02643 - Institut für Theoretische Informatik / Inst. Theoretical Computer Science
Notes
Funding
216071 - Graph coloring motivated by Hadwiger's conjecture (SNF)