complete bipartite graph


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

Author(s): Allagan

\begin{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)$? \end{question}

Keywords: complete bipartite graph; complete multipartite graph; list coloring

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

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.

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

Keywords: complete bipartite graph; crossing number

Syndicate content