complete bipartite graph


List Colourings of Complete Multipartite Graphs with 2 Big Parts ★★

Author(s): Allagan

Question   Given $ a,b\geq2 $, what is the smallest integer $ t\geq0 $ such that $ \chi_\ell(K_{a,b}+K_t)= \chi(K_{a,b}+K_t) $?

Keywords: complete bipartite graph; complete multipartite graph; list 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

The Crossing Number of the Complete Bipartite Graph ★★★

Author(s): Turan

The crossing number $ cr(G) $ of $ G $ is the minimum number of crossings in all drawings of $ G $ in the plane.

Conjecture   $ \displaystyle   cr(K_{m,n}) = \floor{\frac m2} \floor{\frac {m-1}2}                      \floor{\frac n2} \floor{\frac {n-1}2}  $

Keywords: complete bipartite graph; crossing number

Syndicate content