TOPICS
Search

Erdős-Lovász Tihany Conjecture

The Erdős-Lovász Tihany conjecture asserts that if a finite simple graph G satisfies omega(G)<chi(G)=s+t-1 for integers s,t>=2, then its vertex set has a partition into two sets S and T such that

chi(G[S])>=s and chi(G[T])>=t.

Here omega(G) is the clique number, chi(G) is the chromatic number, and G[S] and G[T] are induced subgraphs (Erdős 1968, Song 2026).

The hypothesis excludes complete graphs, whose chromatic number equals their clique number. The conjecture remains open in general; Song (2026) proves it for graphs with no chordless cycle of even length at least 4.

This is problem 628 in the Erdős problems collection (Bloom 2026).

See also

Chromatic Number, Clique Number, Erdős Problems, Induced Subgraph

Explore with Wolfram|Alpha

References

Bloom, T. F. "Erdős Problem 628." Accessed Oct. 26, 2026. https://www.erdosproblems.com/628.Erdős, P. "Problem 2." In Theory of Graphs (Proc. Colloq., Tihany, 1966) (Ed. P. Erdős and G. Katona). New York: Academic Press, p. 361, 1968.Song, Z.-X. "The Erdős-Lovász Tihany Conjecture Holds for All Even-Hole-Free Graphs." 22 Jul 2026. https://arxiv.org/abs/2607.20376.

Cite this as:

Weisstein, Eric W. "Erdős-Lovász Tihany Conjecture." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/Erdos-LovaszTihanyConjecture.html

Subject classifications