Zhao, David


5-coloring graphs with small crossing & clique numbers ★★

Author(s): Oporowski; Zhao

For a graph $G$, we let $cr(G)$ denote the \Def[crossing number]{Crossing number (graph theory)} of $G$, and we let $\omega(G)$ denote the size of the largest complete subgraph of $G$.

\begin{question} Does every graph $G$ with $cr(G) \le 5$ and $\omega(G) \le 5$ have a 5-coloring? \end{question}

Keywords: coloring; crossing number; planar graph

Syndicate content