Erdős Problem #628

Erdős Problem 628 --- collection record

PROVENANCE AND STATUS

Official problem: https://www.erdosproblems.com/628

Saved collaborative-database status: falsifiable. Snapshot checked: 2026-09-23T17:22:24Z. Latest status and formalization links: https://teorth.github.io/erdosproblems/

This is an attributed collection of existing writeups. The model-folder names below identify their original attribution; placement in GPT_6_Astra_Ultra does not attribute their mathematical work to that model. All locally available source versions selected for this problem are reproduced below, without editing their text.

Proof claims, computations, literature statements, and completion estimates in the reused text have not been independently verified in this collection pass. A source claiming a solution does not change the saved upstream status.

Primary source (latest numbered version in the preferred model folder): attacks/erdos/gpt_pro_5.2/628.tex.

REUSED SOURCE 1

Original attribution: gpt_pro_5.2. Original file: attacks/erdos/gpt_pro_5.2/628.tex.

FORMAL RESTATEMENT Let $k\ge3$ and let $G$ be a graph with

• chromatic number $\chi(G)=k$, and
• no clique of size $k$ (i.e., $G$ contains no subgraph isomorphic to $K_k$).

Let $a,b\ge2$ be integers with $a+b=k+1$. The Erdős--Lovász--Tihany conjecture asks whether there exist two vertex-disjoint subgraphs $G_1,G_2\subseteq G$ such that \[ \chi(G_1)\ge a\quad\text{and}\quad \chi(G_2)\ge b. \]

(Here "subgraph" may be taken as induced on its vertex set, since adding edges cannot decrease chromatic number.)

QUICK LITERATURE/CONTEXT CHECK I do not use external sources. The problem file states the conjecture was made in 1981 and is now known in several special cases (including when $\min(a,b)=2$, when $\alpha(G)=2$, and when $G$ is claw-free). I do not assume any of these results in the work below.

ATTACK PLAN First record reductions that make the problem more tractable:

• Replace "two disjoint subgraphs" by a partition of the vertex set into two parts whose induced subgraphs have the required chromatic numbers.
• Reduce to $k$-critical graphs (minimal graphs of chromatic number $k$).

Then prove at least one nontrivial base case (here: $k=3$).

WORK Lemma 1 (equivalent partition formulation). Let $G$ be a graph and let $a,b\ge2$. Then $G$ contains vertex-disjoint subgraphs $G_1,G_2$ with $\chi(G_1)\ge a$ and $\chi(G_2)\ge b$ if and only if there exists a vertex subset $S\subseteq V(G)$ such that \[ \chi\left(G[S]\right)\ge a\quad\text{and}\quad \chi\left(G[V(G)\setminus S]\right)\ge b. \]

Proof. ($\Rightarrow$) Suppose $G_1,G_2$ are vertex-disjoint subgraphs with vertex sets $S:=V(G_1)$ and $T:=V(G_2)$. Then $T\subseteq V(G)\setminus S$, so $G[V(G)\setminus S]$ contains $G_2$ as a subgraph. Chromatic number is monotone under taking supergraphs on the same vertex set (adding edges cannot reduce $\chi$), and also monotone under taking induced supergraphs (adding vertices can only increase or keep $\chi$). Thus \[ \chi(G[V\setminus S]) \ge \chi(G[T]) \ge \chi(G_2) \ge b, \] and by definition $\chi(G[S])\ge \chi(G_1)\ge a$.

($\Leftarrow$) Conversely, if such an $S$ exists, take $G_1:=G[S]$ and $G_2:=G[V\setminus S]$. These are vertex-disjoint induced subgraphs with the required chromatic numbers. $\square$

Lemma 2 (reduction to $k$-critical graphs). Fix $k,a,b$ with $a+b=k+1$. If every $k$-critical graph $H$ with no $K_k$ is $(a,b)$-splittable (in the sense of Lemma 1), then every $k$-chromatic graph $G$ with no $K_k$ is $(a,b)$-splittable.

Proof. Given $G$ with $\chi(G)=k$, there exists an induced subgraph $H\subseteq G$ that is $k$-critical: $\chi(H)=k$ and removing any vertex drops the chromatic number. (Indeed, take an induced subgraph with $\chi=k$ having the minimum number of vertices; it must be $k$-critical.) If $G$ contains no $K_k$, then neither does $H$. By assumption, $H$ is $(a,b)$-splittable, so there is a subset $S\subseteq V(H)$ with $\chi(H[S])\ge a$ and $\chi(H[V(H)\setminus S])\ge b$. Since $H[S]$ and $H[V(H)\setminus S]$ are induced subgraphs of $G$ on disjoint vertex sets, the same subset $S$ witnesses that $G$ is $(a,b)$-splittable. $\square$

Lemma 3 (the conjecture holds for $k=3$). Let $G$ be a graph with $\chi(G)=3$ and containing no $K_3$. Then $G$ is $(2,2)$-splittable, i.e., it contains two vertex-disjoint subgraphs of chromatic number at least $2$.

Proof. Here $k=3$ forces $a=b=2$. A graph has chromatic number at least $2$ iff it contains at least one edge. So it suffices to show that $G$ contains two vertex-disjoint edges, i.e., a matching of size $2$.

Since $\chi(G)=3$, $G$ contains an odd cycle $C$ (otherwise it would be bipartite and 2-colorable). Because $G$ is $K_3$-free, the odd cycle $C$ has length at least $5$ (triangles are excluded). Any cycle of length at least $5$ contains two vertex-disjoint edges, for example on vertices $(v_1,v_2,v_3,v_4,v_5,\dots)$ the edges $v_1v_2$ and $v_3v_4$ are disjoint. These two edges are subgraphs of $G$ with chromatic number $2$ and are vertex-disjoint, proving $(2,2)$-splittability. $\square$

VERIFICATION FAST REALITY CHECK. The smallest $K_3$-free $3$-chromatic graphs are odd cycles $C_{2\ell+1}$ ($\ell\ge2$). For $C_5$, the lemma produces two disjoint edges immediately.

FINAL UNRESOLVED (i) Strongest proved partial results in this write-up: an equivalent partition formulation (Lemma 1), a reduction to $k$-critical graphs (Lemma 2), and a full proof of the conjecture in the first nontrivial case $k=3$ (Lemma 3).

(ii) First gap (crisp): establish the conjecture for $k=4$ (i.e., every $4$-chromatic $K_4$-free graph has a partition into induced subgraphs of chromatic numbers at least $3$ and $2$), and more generally for arbitrary $k$-critical $K_k$-free graphs.

(iii) Top 3 next moves: 1. Work inside $k$-critical graphs (by Lemma 2): exploit standard critical-graph properties (e.g., minimum degree $\ge k-1$) to force the existence of large chromatic induced subgraphs on disjoint vertex sets. 2. Try to prove the $\min(a,b)=2$ case directly from Lemma 1: find an induced $(k-1)$-chromatic subgraph whose complement still contains an edge. 3. Perform small-$n$ computational searches for $k=4,5$ to look for the smallest potential counterexamples and to guess structural invariants that certify splittability.

(iv) Minimal counterexample structure: A minimal counterexample for given $(k,a,b)$ would be a $k$-critical, $K_k$-free graph $G$ such that for every vertex subset $S$ either $\chi(G[S])\le a-1$ or $\chi(G[V\setminus S])\le b-1$. Such a graph would have to be highly constrained: $k$-critical forces $\delta(G)\ge k-1$ and strong connectivity-like behavior, while $K_k$-freeness prevents the usual "obvious" obstructions coming from large cliques.

COMPLETION ESTIMATE

The primary source supplies no extractable numerical completion estimate. Its mathematical progress is not numerically assessed here.

Newly verified progress in this collection pass: $0\%$. This measures new verification work, not the amount of mathematics achieved in the reused text.

FORMAL RESTATEMENT Let $k\ge3$ and let $G$ be a graph with

• chromatic number $\chi(G)=k$, and
• no clique of size $k$ (i.e., $G$ contains no subgraph isomorphic to $K_k$).

Let $a,b\ge2$ be integers with $a+b=k+1$. The Erdős--Lovász--Tihany conjecture asks whether there exist two vertex-disjoint subgraphs $G_1,G_2\subseteq G$ such that \[ \chi(G_1)\ge a\quad\text{and}\quad \chi(G_2)\ge b. \]

(Here "subgraph" may be taken as induced on its vertex set, since adding edges cannot decrease chromatic number.)

QUICK LITERATURE/CONTEXT CHECK I do not use external sources. The problem file states the conjecture was made in 1981 and is now known in several special cases (including when $\min(a,b)=2$, when $\alpha(G)=2$, and when $G$ is claw-free). I do not assume any of these results in the work below.

ATTACK PLAN First record reductions that make the problem more tractable:

• Replace "two disjoint subgraphs" by a partition of the vertex set into two parts whose induced subgraphs have the required chromatic numbers.
• Reduce to $k$-critical graphs (minimal graphs of chromatic number $k$).

Then prove at least one nontrivial base case (here: $k=3$).

WORK Lemma 1 (equivalent partition formulation). Let $G$ be a graph and let $a,b\ge2$. Then $G$ contains vertex-disjoint subgraphs $G_1,G_2$ with $\chi(G_1)\ge a$ and $\chi(G_2)\ge b$ if and only if there exists a vertex subset $S\subseteq V(G)$ such that \[ \chi\left(G[S]\right)\ge a\quad\text{and}\quad \chi\left(G[V(G)\setminus S]\right)\ge b. \]

Proof. ($\Rightarrow$) Suppose $G_1,G_2$ are vertex-disjoint subgraphs with vertex sets $S:=V(G_1)$ and $T:=V(G_2)$. Then $T\subseteq V(G)\setminus S$, so $G[V(G)\setminus S]$ contains $G_2$ as a subgraph. Chromatic number is monotone under taking supergraphs on the same vertex set (adding edges cannot reduce $\chi$), and also monotone under taking induced supergraphs (adding vertices can only increase or keep $\chi$). Thus \[ \chi(G[V\setminus S]) \ge \chi(G[T]) \ge \chi(G_2) \ge b, \] and by definition $\chi(G[S])\ge \chi(G_1)\ge a$.

($\Leftarrow$) Conversely, if such an $S$ exists, take $G_1:=G[S]$ and $G_2:=G[V\setminus S]$. These are vertex-disjoint induced subgraphs with the required chromatic numbers. $\square$

Lemma 2 (reduction to $k$-critical graphs). Fix $k,a,b$ with $a+b=k+1$. If every $k$-critical graph $H$ with no $K_k$ is $(a,b)$-splittable (in the sense of Lemma 1), then every $k$-chromatic graph $G$ with no $K_k$ is $(a,b)$-splittable.

Proof. Given $G$ with $\chi(G)=k$, there exists an induced subgraph $H\subseteq G$ that is $k$-critical: $\chi(H)=k$ and removing any vertex drops the chromatic number. (Indeed, take an induced subgraph with $\chi=k$ having the minimum number of vertices; it must be $k$-critical.) If $G$ contains no $K_k$, then neither does $H$. By assumption, $H$ is $(a,b)$-splittable, so there is a subset $S\subseteq V(H)$ with $\chi(H[S])\ge a$ and $\chi(H[V(H)\setminus S])\ge b$. Since $H[S]$ and $H[V(H)\setminus S]$ are induced subgraphs of $G$ on disjoint vertex sets, the same subset $S$ witnesses that $G$ is $(a,b)$-splittable. $\square$

Lemma 3 (the conjecture holds for $k=3$). Let $G$ be a graph with $\chi(G)=3$ and containing no $K_3$. Then $G$ is $(2,2)$-splittable, i.e., it contains two vertex-disjoint subgraphs of chromatic number at least $2$.

Proof. Here $k=3$ forces $a=b=2$. A graph has chromatic number at least $2$ iff it contains at least one edge. So it suffices to show that $G$ contains two vertex-disjoint edges, i.e., a matching of size $2$.

Since $\chi(G)=3$, $G$ contains an odd cycle $C$ (otherwise it would be bipartite and 2-colorable). Because $G$ is $K_3$-free, the odd cycle $C$ has length at least $5$ (triangles are excluded). Any cycle of length at least $5$ contains two vertex-disjoint edges, for example on vertices $(v_1,v_2,v_3,v_4,v_5,\dots)$ the edges $v_1v_2$ and $v_3v_4$ are disjoint. These two edges are subgraphs of $G$ with chromatic number $2$ and are vertex-disjoint, proving $(2,2)$-splittability. $\square$

VERIFICATION FAST REALITY CHECK. The smallest $K_3$-free $3$-chromatic graphs are odd cycles $C_{2\ell+1}$ ($\ell\ge2$). For $C_5$, the lemma produces two disjoint edges immediately.

FINAL UNRESOLVED (i) Strongest proved partial results in this write-up: an equivalent partition formulation (Lemma 1), a reduction to $k$-critical graphs (Lemma 2), and a full proof of the conjecture in the first nontrivial case $k=3$ (Lemma 3).

(ii) First gap (crisp): establish the conjecture for $k=4$ (i.e., every $4$-chromatic $K_4$-free graph has a partition into induced subgraphs of chromatic numbers at least $3$ and $2$), and more generally for arbitrary $k$-critical $K_k$-free graphs.

(iii) Top 3 next moves: 1. Work inside $k$-critical graphs (by Lemma 2): exploit standard critical-graph properties (e.g., minimum degree $\ge k-1$) to force the existence of large chromatic induced subgraphs on disjoint vertex sets. 2. Try to prove the $\min(a,b)=2$ case directly from Lemma 1: find an induced $(k-1)$-chromatic subgraph whose complement still contains an edge. 3. Perform small-$n$ computational searches for $k=4,5$ to look for the smallest potential counterexamples and to guess structural invariants that certify splittability.

(iv) Minimal counterexample structure: A minimal counterexample for given $(k,a,b)$ would be a $k$-critical, $K_k$-free graph $G$ such that for every vertex subset $S$ either $\chi(G[S])\le a-1$ or $\chi(G[V\setminus S])\le b-1$. Such a graph would have to be highly constrained: $k$-critical forces $\delta(G)\ge k-1$ and strong connectivity-like behavior, while $K_k$-freeness prevents the usual "obvious" obstructions coming from large cliques.