graph coloring

Exact colorings of graphs ★★

Author(s): Erickson

\begin{conjecture} For $c \geq m \geq 1$, let $P(c,m)$ be the statement that given any exact $c$-coloring of the edges of a complete countably infinite graph (that is, a coloring with $c$ colors all of which must be used at least once), there exists an exactly $m$-colored countably infinite complete subgraph. Then $P(c,m)$ is true if and only if $m=1$, $m=2$, or $c=m$. \end{conjecture}

Keywords: graph coloring; ramsey theory

3-Colourability of Arrangements of Great Circles ★★

Author(s): Felsner; Hurtado; Noy; Streinu

Consider a set $S$ of great circles on a sphere with no three circles meeting at a point. The arrangement graph of $S$ has a vertex for each intersection point, and an edge for each arc directly connecting two intersection points. So this arrangement graph is 4-regular and planar.

\begin{conjecture} Every arrangement graph of a set of great circles is $3$-colourable. \end{conjecture}

Keywords: arrangement graph; graph coloring

Syndicate content