Home » Keyword index

interlacing


Graph Theory » Coloring » Vertex coloring

Alon-Saks-Seymour Conjecture ★★★

Author(s): Alon; Saks; Seymour

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 $.

Keywords: coloring; complete bipartite graph; eigenvalues; interlacing

Posted by mdevos
updated February 26th, 2010
1 comment
Syndicate content