planar graphs


Nonrepetitive colourings of planar graphs ★★

Author(s): Alon N.; Grytczuk J.; Hałuszczak M.; Riordan O.

\begin{question} Do planar graphs have bounded nonrepetitive chromatic number? \end{question}

Keywords: nonrepetitive colouring; planar graphs

Circular choosability of planar graphs

Author(s): Mohar

Let $G = (V, E)$ be a graph. If $p$ and $q$ are two integers, a $(p,q)$-colouring of $G$ is a function $c$ from $V$ to $\{0,\dots,p-1\}$ such that $q \le |c(u)-c(v)| \le p-q$ for each edge $uv\in E$. Given a list assignment $L$ of $G$, i.e.~a mapping that assigns to every vertex $v$ a set of non-negative integers, an $L$-colouring of $G$ is a mapping $c : V \to N$ such that $c(v)\in L(v)$ for every $v\in V$. A list assignment $L$ is a $t$-$(p,q)$-list-assignment if $L(v) \subseteq \{0,\dots,p-1\}$ and $|L(v)| \ge tq$ for each vertex $v \in V$ . Given such a list assignment $L$, the graph G is $(p,q)$-$L$-colourable if there exists a $(p,q)$-$L$-colouring $c$, i.e. $c$ is both a $(p,q)$-colouring and an $L$-colouring. For any real number $t \ge 1$, the graph $G$ is $t$-$(p,q)$-choosable if it is $(p,q)$-$L$-colourable for every $t$-$(p,q)$-list-assignment $L$. Last, $G$ is circularly $t$-choosable if it is $t$-$(p,q)$-choosable for any $p$, $q$. The circular choosability (or circular list chromatic number or circular choice number) of G is $$cch(G) := \inf\{t \ge 1 : G \text{ is circularly $t$-choosable}\}.$$

\begin{problem} What is the best upper bound on circular choosability for planar graphs? \end{problem}

Keywords: choosability; circular colouring; planar graphs

Syndicate content