Abstract: The Erdős-Lovász Tihany Conjecture states that for any pair of integers $s, t \ge 2$ and for any graph $G$ with chromatic number equal to $s + t - 1$ and clique number less than $s + t - 1$, there are two disjoint subgraphs of $G$ with chromatic number $s$ and $t$, respectively. This conjecture remains open except for a few small values of $s$ and $t$. Given the same hypothesis, this paper studies the problem of finding two disjoint subgraphs of $G$ with complete minors of order $s$ and $t$, respectively. By leveraging structural graph theory and techniques related to Hadwiger's Conjecture, we settle this relaxed problem for several additional values of $s$ and $t$ in 7, 8, and 9-chromatic graphs.
Introduction
In 1968, Paul Erdős and László Lovász proposed a deep conjecture regarding the distribution of "color-demanding" structures within a graph. The Erdős-Lovász Tihany (ELT) Conjecture posits that if a graph $G$ has a chromatic number $\chi(G) = s + t - 1$ but does not contain a clique of that size ($\omega(G) < s + t - 1$), it must contain two vertex-disjoint subgraphs, $G_1$ and $G_2$, such that $\chi(G_1) \ge s$ and $\chi(G_2) \ge t$.
Despite its simple formulation, the conjecture is notoriously difficult. This paper, published in the Journal of Combinatorics, addresses a relaxed version: instead of requiring $G_1$ and $G_2$ to have high chromatic numbers, the authors investigate whether $G_1$ and $G_2$ must contain complete minors of order $s$ and $t$. This version is intimately tied to Hadwiger’s Conjecture, which suggests that every $k$-chromatic graph contains a $K_k$ minor. If Hadwiger's Conjecture holds, this minor-based relaxation should be more tractable than the original ELT Conjecture.
Methodological Approach
The research employs purely theoretical proofs rooted in structural graph theory. The authors primarily utilize a minimum counterexample strategy, assuming a graph exists that violates the conjecture with the fewest possible vertices and then deriving a logical contradiction from its properties.
Key techniques include:
- Vertex Partitioning: Utilizing theorems by Stiebitz regarding degree and coloring constraints to split graphs into disjoint components.
- Minor Theory: Leveraging established results on $K_5$ and $K_6$ minors—which are fundamentally linked to the Four Color Theorem—to build up to larger structures.
- Kempe Chains: A classical coloring technique used to show that if a certain coloring exists, it can be modified to satisfy the conjecture's requirements, thereby proving the counterexample cannot exist.
Key Insights and Results
The authors argue that the "minor" version of the conjecture is more accessible because it allows for the use of powerful structural tools developed for Hadwiger’s Conjecture. A recurring theme in the proofs is the analysis of the neighborhood of a vertex $u$; if the neighborhood $N(u)$ can be covered by two cliques (bisimplicial), the graph's structure becomes significantly more restricted, facilitating the identification of minors.
The paper successfully settles the relaxed conjecture for several specific configurations in high-chromatic graphs:
- 7-Chromatic Graphs: Every 7-chromatic graph with $\omega(G) \le 6$ contains disjoint subgraphs with $K_s$ and $K_t$ minors for $(s, t) \in \{(2, 6), (3, 5), (4, 4)\}$.
- 8-Chromatic Graphs: The authors settled the case for $(s, t) = (2, 7)$, as well as the existence of $K_{4,5}$ and $K_{3,6}$ minors.
- 9-Chromatic Graphs: Every 9-chromatic graph with $\omega(G) \le 8$ contains either a $K_{4,6}$ or a $K_{5,5}$ minor.
Additionally, the paper highlights the importance of double-critical graphs. The ELT Conjecture for $s=2$ is equivalent to the Double-Critical Graph Conjecture, which suggests that the only graphs where the removal of any two adjacent vertices decreases the chromatic number by two are complete graphs.
Limitations and Future Work
While these results extend the boundary of structural decomposition, they remain partially dependent on the broader context of Hadwiger’s Conjecture. If Hadwiger’s is eventually proven false, the "relaxed" version might prove to be as difficult as the original. Furthermore, much of the current progress relies on case-by-case analysis for specific chromatic numbers (7, 8, 9). A unified, general proof for all $s$ and $t$ remains the ultimate goal. Finally, the authors note that the conjecture remains particularly challenging for triangle-free graphs, where the lack of small cliques limits the available structural evidence for large minors.
Summary updated