Home » Subject » Graph Theory » Coloring » Vertex coloring
Importance: High ✭✭✭
Author(s): Erdos, Paul
Faber, Vance
Lovasz, Laszlo
Subject: Graph Theory
» Coloring
» » Vertex coloring
Keywords: chromatic number
Recomm. for undergrads: no
Prize: $500 (Erdos)
Posted by: Jon Noel
on: August 22nd, 2013
Conjecture   If $ G $ is a simple graph which is the union of $ k $ pairwise edge-disjoint complete graphs, each of which has $ k $ vertices, then the chromatic number of $ G $ is $ k $.

From [Erd81]: "Faber, Lovász and I made this harmless looking conjecture at a party in Boulder Colorado in September 1972. Its diffculty was realised only slowly. I now offer 500 dollars for a proof or disproof. (Not long ago I only offered 50; the increase is not due to inflation but to the fact that I now think the problem is very diffcult. Perhaps I am wrong.)"

The conjecture can be equivalently formulated in terms of seating assignments or hypergraph colouring; see Wikipedia or Doug West's Webpage.

Related problems

Alon-Saks-Seymour Conjecture

Bibliography

[Erd81] P. Erdős. On the combinatorial problems which I would most like to see solved. Combinatorica, 1(1):25–42, 1981.


* indicates original appearance(s) of problem.
add new comment

Reply

Comments are limited to a maximum of 1000 characters.
More information about formatting options