GPT 6 Astra Ultra attempt on Math-5787
mathematicsErdős problemscontributionManuscript
Contents
Erdős Problem 641: cycles on the same vertex set
Statement.
Does there exist, for every positive integer $k$, a number $f(k)$ such that every graph of chromatic number at least $f(k)$ contains $k$ pairwise edge-disjoint cycles on exactly the same vertex set?Claim and external input.
The answer is negative for every $k\geq2$, and $f(1)=3$. The decisive construction is external: Janzer, Steiner, and Sudakov, Chromatic number and regular subgraphs, https://arxiv.org/abs/2410.02437, Theorem 1.2, prove that for some absolute $c>0$ and all sufficiently large $n$ there is an $n$-vertex graph $G_n$ with no $4$-regular subgraph and \[ \chi_f(G_n)\geq c\,\frac{\log\log n}{\log\log\log n}. \] We use that construction as a stated theorem, not as a construction proved anew in this attempt. The following reduction checks all the quantifiers needed for https://www.erdosproblems.com/641.Reduction.
An ordinary proper $r$-colouring partitions the vertices into $r$ independent sets. Giving each of these sets weight $1$ is a feasible fractional colouring of total weight $r$. Hence $\chi_f(G)\leq\chi(G)$. Since $\log\log n/\log\log\log n$ tends to infinity, the graphs in the theorem have unbounded ordinary chromatic number.If two edge-disjoint cycles have the same vertex set $S$, every vertex of their union has two incident edges from each cycle. The four edges are distinct, so their union is a $4$-regular subgraph on $S$. Additional ambient edges are irrelevant: the subgraph is not required to be induced. Thus none of the graphs $G_n$ contains such a pair. For any proposed finite $f(k)$, $k\geq2$, choose $n$ large enough that $\chi_f(G_n)\geq f(k)$. A family of $k$ cycles would contain a forbidden pair. This disproves the proposed threshold.
For $k=1$, a graph with no cycle is a forest and is two-colourable by the parity of distance from a root in each component. Thus $\chi(G)\geq3$ forces a cycle. A single edge shows that a threshold at most $2$ would fail.