This record is in review state, the data has not yet been validated.
This is not the latest version of this item. The latest version can be found here.
Chromatic number and regular subgraphs
Loading...
Author / Producer
Date
2025-12-17
Publication Type
Journal Article
ETH Bibliography
Data
Rights / License
Abstract
In 1992, Erd & odblac;s and Hajnal posed the following natural problem: Does there exist, for every , an integer such that every graph with chromatic number at least contains edge-disjoint cycles on the same vertex set? We solve this problem in a strong form, by showing that there exist -vertex graphs with fractional chromatic number that do not even contain a 4-regular subgraph. This implies that no such number exists for . We show that, assuming a conjecture of Harris, the bound on the fractional chromatic number in our result cannot be improved. (After our paper was written, Harris' conjecture was proved by Martinsson.)
Permanent link
Publication status
External links
Editor
Book title
Journal / series
BULLETIN OF THE LONDON MATHEMATICAL SOCIETY