Erdős–Faber–Lovász conjecture

Definitions and mathematical statement

Shared notation.

$\mathbb N=\{1,2,\ldots\}$, and $\mathbb Z,\mathbb Q,\mathbb R,\mathbb C$ denote the integers, rationals, reals and complex numbers. Any other conventions are specified locally.

Let $k\ge1$, and let $G$ be the union of $k$ complete subgraphs $Q_1,\ldots,Q_k$, each on $k$ vertices, such that their edge sets are pairwise disjoint. Thus $V(G)=\bigcup_iV(Q_i)$ and $E(G)=\bigcup_iE(Q_i)$; different $Q_i$ may share vertices. Let $\chi(G)$ be the proper vertex chromatic number.

Statement recorded in the supplied source.

Must every such finite simple graph satisfy $\chi(G)=k$? [S2]

Short English statement

Can the union of k edge-disjoint cliques of order k always be colored with k colors?

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, UnsolvedMath: A Curated Collection of Open Mathematics Problems, record 3250 (OPG-55984). CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Open Problem Garden, Erdős–Faber–Lovász conjecture, original node 55984, statement and mathematical discussion. https://www.openproblemgarden.org/op/erdos_faber_lovasz_conjecture.