interlacing


Alon-Saks-Seymour Conjecture ★★★

Author(s): Alon; Saks; Seymour

\begin{conjecture} If $G$ is a simple graph which can be written as an union of $m$ edge-disjoint complete bipartite graphs, then $\chi(G) \le m+1$. \end{conjecture}

Keywords: coloring; complete bipartite graph; eigenvalues; interlacing

Syndicate content