Erdős–Faber–Lovász conjecture

The conjecture that the union of any n graphs, each with n vertices and any two sharing at most one vertex, has chromatic number at most n.

Graph coloring: The assignment of colors to graph vertices so adjacent vertices receive different colors. The conjecture asks whether the union can always be colored using at most n colors.
Linear hypergraph: A hypergraph in which any two distinct edges intersect in at most one vertex. The conjecture is equivalent to bounding the chromatic number of line graphs of linear hypergraphs.
Paul Erdős: A Hungarian mathematician known for prolific work in combinatorics, number theory, and probability. He posed the coloring problem with V. Faber and L. Lovász.
Erdős–Faber–Lovász theorem: The proved statement that a union of n n-vertex graphs with pairwise intersections of at most one vertex is n-colorable. The conjecture became a theorem after the proof announced in 2021.
Chromatic number: The minimum number of colors needed to color a graph so adjacent vertices have different colors. This is the quantity bounded by n in the conjecture.
Edge coloring: An assignment of colors to graph edges so edges sharing a vertex receive different colors. Coloring the hyperedges is the same as coloring vertices of their line graph.
Václav Chvátal: A Czech-Canadian mathematician whose work includes graph theory and combinatorial optimization. He publicized the problem in the early 1970s, helping establish its enduring name.
Erdős–Faber–Lovász problem: A graph-coloring problem asking for an n-coloring of unions of n n-vertex graphs with pairwise intersections at most one vertex. This common name emphasizes the problem itself, including the long path from conjecture to proof.
Hypergraph: A generalization of a graph in which an edge can contain any number of vertices. The graphs can be viewed as complete hyperedges whose pairwise intersections contain at most one vertex.
List coloring: A graph-coloring problem in which each vertex has an individual list of allowed colors. List-coloring variants strengthen the basic bound and appear in proofs of the conjecture.

Linked from 1 page