# complete graph

## Star chromatic index of complete graphs ★★

Author(s): Dvorak; Mohar; Samal

\begin{conjecture} Is it possible to color edges of the complete graph $K_n$ using $O(n)$ colors, so that the coloring is proper and no 4-cycle and no 4-edge path is using only two colors?

Equivalently: is the star chromatic index of $K_n$ linear in $n$? \end{conjecture}

Keywords: complete graph; edge coloring; star coloring

## Crossing numbers and coloring ★★★

Author(s): Albertson

We let $cr(G)$ denote the \Def[crossing number]{crossing number (graph theory)} of a graph $G$.

\begin{conjecture} Every graph $G$ with $\chi(G) \ge t$ satisfies $cr(G) \ge cr(K_t)$. \end{conjecture}

Keywords: coloring; complete graph; crossing number

## Double-critical graph conjecture ★★

Author(s): Erdos; Lovasz

A connected simple graph $G$ is called double-critical, if removing any pair of adjacent vertexes lowers the \Def{chromatic number} by two.

\begin{conjecture} $K_n$ is the only $n$-chromatic double-critical graph \end{conjecture}

Keywords: coloring; complete graph

## Seagull problem ★★★

Author(s): Seymour

\begin{conjecture} Every $n$ vertex graph with no independent set of size $3$ has a complete graph on $\ge \frac{n}{2}$ vertices as a minor. \end{conjecture}

Keywords: coloring; complete graph; minor

## Coloring and immersion ★★★

Author(s): Abu-Khzam; Langston

\begin{conjecture} For every positive integer $t$, every (loopless) graph $G$ with $\chi(G) \ge t$ immerses $K_t$. \end{conjecture}

Keywords: coloring; complete graph; immersion

## The Crossing Number of the Complete Graph ★★★

Author(s):

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_n) = \frac 14 \floor{\frac n2} \floor{\frac{n-1}2} \floor{\frac{n-2}2} \floor{\frac{n-3}2}$ \end{conjecture}

Keywords: complete graph; crossing number