\documentclass[12pt]{article} \usepackage{e-jc} \usepackage{amsmath,amsthm,amsfonts,amssymb,enumerate,graphicx,float,calc} \usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref} \usepackage{algorithm} \usepackage{algorithmic} \floatname{algorithm}{Algorithm} \renewcommand{\algorithmicrequire}{\textbf{Input:}} \renewcommand{\algorithmicensure}{\textbf{Output:}} \usepackage[numbers,sort&compress]{natbib} %\sloppy \DeclareMathOperator{\layer}{layer} \DeclareMathOperator{\depth}{depth} \DeclareMathOperator{\blah}{col} \renewcommand{\thefootnote}{\fnsymbol{footnote}} \allowdisplaybreaks \newcommand{\arXiv}[1]{arXiv:\,\href{http://arxiv.org/abs/#1}{#1}} \newcommand{\msn}[1]{MR:\,\href{http://www.ams.org/mathscinet-getitem?mr=MR#1}{#1}} \newcommand{\MSN}[2]{MR:\,\href{http://www.ams.org/mathscinet-getitem?mr=MR#1}{#1}} \newcommand{\doi}[1]{doi:\,\href{http://dx.doi.org/#1}{#1}} \theoremstyle{plain} \newtheorem{theorem}{Theorem} \newtheorem{lemma}[theorem]{Lemma} \date{\dateline{Feb 17, 2012}{Feb 19, 2013}{}\\ \small Mathematics Subject Classifications: 05C15; 05C10} \begin{document} \author{ Vida Dujmovi{\'c}\,\footnotemark[2] \quad Fabrizio Frati\,\footnotemark[3] \quad Gwena\"el Joret\,\footnotemark[4] \quad David~R.~Wood\,\footnotemark[5]} \footnotetext[2]{School of Mathematics and Statistics \& Department of Systems and Computer Engineering, Carleton University, Ottawa, Canada (\texttt{vdujmovic@math.carleton.ca}). Supported by NSERC and an Endeavour Fellowship from the Australian Government.} \footnotetext[3]{School of Information Technologies, The University of Sydney, Sydney, Australia (\texttt{brillo@it.usyd.edu.au}).} \footnotetext[4]{D\'epartement d'Informatique, Universit\'e Libre de Bruxelles, Brussels, Belgium (\texttt{gjoret@ulb.ac.be}). Supported by an Endeavour Fellowship from the Australian Government.} \footnotetext[5]{School of Mathematical Sciences, Monash University, Melbourne, Australia (\texttt{david.wood@monash.edu}). Research supported by the Australian Research Council.} \title{\boldmath\bf Nonrepetitive Colourings of Planar Graphs\\ with $O(\log n)$ Colours} \maketitle % \thanks{\textbf{MSC Classification}: ???} \begin{abstract} A vertex colouring of a graph is \emph{nonrepetitive} if there is no path for which the first half of the path is assigned the same sequence of colours as the second half. The \emph{nonrepetitive chromatic number} of a graph $G$ is the minimum integer $k$ such that $G$ has a nonrepetitive $k$-colouring. Whether planar graphs have bounded nonrepetitive chromatic number is one of the most important open problems in the field. Despite this, the best known upper bound is $O(\sqrt{n})$ for $n$-vertex planar graphs. We prove a $O(\log n)$ upper bound. \end{abstract} \section{Introduction} \renewcommand{\thefootnote}{\arabic{footnote}} % \footnote{We consider simple, finite, undirected graphs $G$ with % vertex set $V(G)$, edge set $E(G)$, maximum degree $\Delta(G)$, % and maximum clique size $\omega(G)$. The \emph{neighbourhood} of a % vertex $v\in V(G)$ is $N_G(v):=\{w\in V(G):vw\in E(G)\}$. The % \emph{neighbourhood} of a set $S\subseteq V(G)$ is % $N_G(S):=\bigcup\{N_G(x):x\in S\}- S$. The degree of a % vertex $v\in V(G)$ is $\deg_G(v):=|N_G(v)|$. We use $N(v)$ and % $N(S)$ and $\deg(v)$ if the graph $G$ is clear from the context.} A vertex colouring of a graph is \emph{nonrepetitive} if there is no path for which the first half of the path is assigned the same sequence of colours as the second half. More precisely, a $k$-\emph{colouring} of a graph $G$ is a function $\psi$ that assigns one of $k$ colours to each vertex of $G$. A path $(v_1,v_2,\dots,v_{2t})$ of even order in $G$ is \emph{repetitively} coloured by $\psi$ if $\psi(v_i)=\psi(v_{t+i})$ for all $i\in[1,t]:=\{1,2,\dots,t\}$. A colouring $\psi$ of $G$ is \emph{nonrepetitive} if no path of $G$ is repetitively coloured by $\psi$. Observe that a nonrepetitive colouring is \emph{proper}, in the sense that adjacent vertices are coloured differently. The \emph{nonrepetitive chromatic number} $\pi(G)$ is the minimum integer $k$ such that $G$ admits a nonrepetitive $k$-colouring. The seminal result in this field is by \citet{Thue06}, who in 1906 proved % \footnote{The nonrepetitive $3$-colouring of $P_n$ by \citet{Thue06} % is obtained as follows. Given a nonrepetitive sequence over % $\{1,2,3\}$, replace each $1$ by the sequence $12312$, replace % each $2$ by the sequence $131232$, and replace each $3$ by the % sequence $1323132$. \citet{Thue06} proved that the new sequence is % nonrepetitive. Thus arbitrarily long paths can be nonrepetitively % $3$-coloured.} that every path is nonrepetitively 3-colourable. Nonrepetitive colourings have recently been widely studied%\citep{HJ-DM11,Currie-EJC02,HJSS,PZ09,BreakingRhythm,BC11,BaratWood-EJC08,BV-NonRepVertex07,BK-AC04,GKM11,BGKNP-NonRepTree-DM07,Grytczuk,Currie-TCS05,Manin,Rampersad,NOW,KP-DM08,FOOZ,Pegden11,BV-NonRepEdge08,CG-ENDM07,Grytczuk-EJC02,AGHR-RSA02,GPZ, % JS09,DS09} ; see the surveys \citep{Gryczuk-IJMMS07,Grytczuk-DM08,CSZ}. %Grytczuk, A number of graph classes are known to have bounded nonrepetitive chromatic number. In particular, trees are nonrepetitively 4-colourable \citep{BGKNP-NonRepTree-DM07,KP-DM08}, outerplanar graphs are nonrepetitively $12$-colourable \citep{KP-DM08,BV-NonRepVertex07}, and more generally, every graph with treewidth $k$ is nonrepetitively $4^k$-colourable \citep{KP-DM08}. Graphs with maximum degree $\Delta$ are nonrepetitively $O(\Delta^2)$-colourable \citep{AGHR-RSA02,Gryczuk-IJMMS07,HJ-DM11,NonRep}. %Grytczuk, Perhaps the most important open problem in the field of nonrepetitive colourings is whether planar graphs have bounded nonrepetitive chromatic number. This question, first asked by \citet{AGHR-RSA02}, has since been mentioned by numerous authors \citep{Grytczuk-DM08,Gryczuk-IJMMS07,KP-DM08,GPZ,BV-NonRepVertex07,BreakingRhythm,HJ-DM11,Grytczuk-EJC02,NOW,CG-ENDM07,DS09}. % Grytczuk, It is widely known that $\pi(G)\in O(\sqrt{n})$ for $n$-vertex planar graphs\footnote{One can prove this bound using a naive application of the Lipton-Tarjan planar separator theorem.}, and this is the best known upper bound. The best known lower bound is $11$, due to Pascal Ochem; see Appendix~\ref{LowerBound}. Here we prove a logarithmic upper bound. \begin{theorem} \label{NonRepPlanar} For every planar graph $G$ with $n$ vertices,$$\pi(G)\leq 8(1+\log_{3/2}n)\enspace.$$ \end{theorem} We now explain that the above open problem is solved when restricted to paths of bounded length. For $p\geq 1$, a vertex colouring of a graph $G$ is \emph{$p$-centered} if for every connected subgraph $X$ of $G$, some colour appears appears exactly once in $X$, or at least $p$ colours appear in $X$. In a repetitively coloured path of at most $2p-2$ vertices, there are at most $p-1$ colours each appearing at least twice. Thus the colouring is not $p$-centered. Equivalently, every $p$-centered colouring is nonrepetitive on paths with at most $2p-2$ vertices. \citet{NO06} proved that for every graph $H$ and integer $p\geq1$, there exists an integer $c$, such that every graph with no $H$-minor has a $p$-centered colouring with $c$ colours. %Such a colouring is nonrepetitive on paths with at most $2p-2$ vertices. This shows that (with $H=K_5$) for every integer $p\geq1$, there exists an integer $c$, such that every planar graph has a $c$-colouring that is nonrepetitive on paths with at most $2p$ vertices. Note that the bound on $c$ in terms of $p$ here is large. It is open whether there is a polynomial function $f$ such that for every integer $k\geq 1$ every planar graph $G$ has a $f(k)$-colouring that is nonrepetitive on paths with most $2k$ vertices. Finally, we mention a class of planar graphs that seem difficult to nonrepetitively colour. Let $T$ be a tree rooted at a vertex $r$. Let $V_i$ be the set of vertices in $T$ at distance $i$ from $r$. Draw $T$ in the plane with no crossings. Add a cycle on each $V_i$ in the cyclic order defined by the drawing to create a planar graph $G_T$. It is open whether $\pi(G_T)\leq c$ for some constant $c$ independent of $T$. Note that this class of planar graphs includes examples with unbounded degree and unbounded treewidth. %As a secondary contribution, we solve the above open problem when restricted to paths of bounded length. % %\begin{theorem} % \label{LocalPlanar} % There is a constant $c$ such that, for every integer $k\geq 1$, % every planar graph $G$ is $c^{k^2}$-colourable such that $G$ % contains no repetitively coloured path of order at most $2k$. %\end{theorem} % %Note that the case $k=2$ of Theorem~\ref{LocalPlanar} corresponds to %so-called \emph{star colourings}; that is, proper colourings with no %2-coloured $P_4$; see %\citep{Albertson-EJC04,FRR-JGT04,NesOdM-03,Wood-DMTCS05}. \citet{Albertson-EJC04} %proved that every planar graph is star colourable with 20 colours. \section{Proof of Theorem~\ref{NonRepPlanar}} A \emph{layering} of a graph $G$ is a partition $V_0,V_1,\dots,V_p$ of $V(G)$ such that for every edge $vw\in E(G)$, if $v\in V_i$ and $w\in V_j$ then $|i-j|\leq 1$. Each set $V_i$ is called a \emph{layer}. The following lemma by \citet{KP-DM08} will be useful. % A \emph{layering} of $G$ is a function % $\layer:V(G)\rightarrow\mathbb{N}$ such that % $|\layer(v)-\layer(w)|\leq 1$ for every edge $vw\in E(G)$. Let % $V_i:=\layer^{-1}(i)$. Then $V_1,V_2,\dots$ are called % \emph{layers}. % \begin{lemma}[\cite{KP-DM08}] \label{Pattern} Let % $V_1,V_2,\dots,V_p$ be a layering of a graph $G$. Let % $\alpha_1,\alpha_2,\dots,\alpha_t$ be a nonrepetitive % palindrome-free sequence (of four symbols). Colour each vertex % $v\in V_i$ by $\alpha_i$. If $(v_1,v_2,\dots,v_{2r})$ is a % repetitively coloured path in $G$ then $(v_1,v_2,\dots,v_{r})$ and % $(v_{r+1},v_{r+2},\dots,v_{2r})$ have the same layer pattern. % \end{lemma} \begin{lemma}[\cite{KP-DM08}] \label{Pattern} For every layering of a graph $G$, there is a (not necessarily proper) 4-colouring of $G$ such that %all the vertices in each layer $V_i$ get the same colour, and for every repetitively coloured path $(v_1,v_2,\dots,v_{2t})$, the subpaths $(v_1,v_2,\dots,v_{t})$ and $(v_{t+1},v_{t+2},\dots,v_{2t})$ have the same layer pattern. \end{lemma} A \emph{separation} of a graph $G$ is a pair $(G_1,G_2)$ of subgraphs of $G$, such that $G=G_1\cup G_2$. In particular, there is no edge of $G$ between $V(G_1)-V(G_2)$ and $V(G_2)-V(G_1)$. \begin{lemma} \label{General} Fix $\varepsilon\in(0,1)$ and $c\geq 1$. Let $G$ be a graph with $n$ vertices. Fix a layering $V_0,V_1,\dots,V_p$ of $G$. Assume that, for every set $B\subseteq V(G)$, there is a separation $(G_1,G_2)$ of $G$ such that: \begin{itemize} \item each layer $V_i$ contains at most $c$ vertices in $V(G_1)\cap V(G_2)\cap B$, and \item both $V(G_1)-V(G_2)$ and $V(G_2)-V(G_1)$ contain at most $(1-\varepsilon)|B|$ vertices in $B$. \end{itemize} Then $\pi(G)\leq 4c(1+\log_{1/(1-\varepsilon)}n)$. \end{lemma} \begin{proof} Run the following recursive algorithm \textsc{Compute}$(V(G),1)$. \begin{center} \framebox{ \begin{minipage}{\textwidth-8mm} \medskip \textsc{Compute}$(B,d)$ \hspace*{-1.5em} \begin{minipage}{\textwidth+1mm} \medskip \begin{enumerate} \item If $B=\emptyset$ then exit. \item Let $(G_1,G_2)$ be a separation of $G$ such that each layer $V_i$ contains at most $c$ vertices in $V(G_1)\cap V(G_2)\cap B$, and both $V(G_1)-V(G_2)$ and $V(G_2)-V(G_1)$ contain at most $(1-\varepsilon)|B|$ vertices in $B$. \item Let $\depth(v):=d$ for each vertex $v\in V(G_1)\cap V(G_2)\cap B$. \item For $i\in[1,p]$, injectively label the vertices in $V_i\cap V(G_1)\cap V(G_2)\cap B$ by $1,2,\dots,c$.\\ Let $\textup{label}(v)$ be the label assigned to each vertex $v\in V_i\cap V(G_1)\cap V(G_2)\cap B$. \item\textsc{Compute}$((V(G_1)-V(G_2))\cap B,d+1)$ \item \textsc{Compute}$((V(G_2)-V(G_1))\cap B,d+1)$ \smallskip \end{enumerate} \end{minipage} \end{minipage}} \end{center} \bigskip The recursive application of \textsc{Compute} determines a rooted binary tree $T$, where each node of $T$ corresponds to one call to \textsc{Compute}. Associate each vertex whose depth and label is computed in a particular call to \textsc{Compute} with the corresponding node of $T$. (Observe that the depth and label of each vertex is determined exactly once.) Colour each vertex $v$ by $(\blah(v),\depth(v),\textup{label}(v))$, where $\blah$ is the 4-colouring from Lemma~\ref{Pattern}. Suppose on the contrary that $(v_1,v_2,\dots,v_{2t})$ is a repetitively coloured path in $G$. By Lemma~\ref{Pattern}, $(v_1,v_2,\dots,v_{t})$ and $(v_{t+1},v_{t+2},\dots,v_{2t})$ have the same layer pattern. In addition, $\depth(v_i)=\depth(v_{t+i})$ and $\textup{label}(v_{i})=\textup{label}(v_{t+i})$ for all $i\in[1,t]$. Let $v_i$ and $v_{t+i}$ be vertices in this path with minimum depth. Since $v_i$ and $v_{t+i}$ are in the same layer and have the same label, these two vertices were not labelled at the same step of the algorithm. Let $x$ and $y$ be the two nodes of $T$ respectively associated with $v_i$ and $v_{t+i}$. Let $z$ be the least common ancestor of $x$ and $y$ in $T$. Say node $z$ corresponds to call \textsc{Compute}$(B,d)$. Thus $v_i$ and $v_{t+i}$ are in $B$ (since if a vertex $v$ is in $B$ in the call to $\textsc{Compute}$ associated with some node $q$ of $T$, then $v$ is in $B$ in the call to $\textsc{Compute}$ associated with each ancestor of $q$ in $T$). Let $(G_1,G_2)$ be the separation in \textsc{Compute}$(B,d)$. Since $\depth(v_i)=\depth(v_{t+i})>d$, neither $v_i$ nor $v_{t+i}$ are in $V(G_1)\cap V(G_2)$. Since $z$ is the least common ancestor of $x$ and $y$, without loss of generality, $v_i\in V(G_1)-V(G_2)$ and $v_{t+i}\in V(G_2)-V(G_1)$. % if t_1 and t_2 are siblings in T and if B(t_1) and B(t_2) are the % sets B for the calls to COMPUTE associated with nodes t_1 and t_2, % then B(t_1) \cap B(t_2) = \emptyset. Thus some vertex $v_j$ in the subpath $(v_{i+1},v_{i+2},\dots,v_{t+i-1})$ is in $V(G_1)\cap V(G_2)$. If $v_j\in B$ then $\depth(v_j)=d$. If $v_j\not\in B$ then $\depth(v_j)\frac{2}{3}|B|$. Thus $r_B(S)<\frac{1}{3}|B|$. We distinguish the following cases: \bigskip \emph{Case~1.} $S=(u_0,u_1,\dots,u_{k-1},u_k,v_k,v_{k-1},\dots,v_1,v_0)$: Let $w$ be the vertex that forms a face $f=(u_k,w,v_k)$ in clockwise order. By the definition of layering, $w\in V_{k+1}\cup V_k\cup V_{k-1}$. \emph{Case~1(a).} $w\in V_{k+1}$: Then $S':=(u_0,u_1,\dots,u_{k-1},u_k,w,v_k,v_{k-1},\dots,v_1,v_0)$ is a lollipop. Since $f$ is a face, $R_B(S')=R_B(S)$ and $L(S')=L(S)-\{w\}$, contradicting (3). \emph{Case~1(b).} $w=u_{k-1}$: Observe that $S':=(u_0,u_1,\dots,u_{k-1},v_k,v_{k-1},\dots,v_1,v_0)$ is a lollipop of height $k-1$. We have $r_B(S')\leq r_B(S)+1<\frac{1}{3}|B|+1\leq \frac{2}{3}|B|$ (since $|B|\geq3$). Hence $S'$ satisfies (1). If $u_k\in B$ then $r_B(S')>r_B(S)$, contradicting (2). Now assume that $u_k\not\in B$. We have $\ell(S')=\ell(S)$ and $r(S')=r(S)+1$, contradicting (4). \emph{Case~1(c).} $w=v_{k-1}$: This case is analogous to Case~1(b) except that we use $S':=(u_0,u_1,\dots,u_{k-1},u_k,v_{k-1},\dots,v_1,v_0)$. \emph{Case~1(d).} $w\in V_{k-1}-\{u_{k-1},v_{k-1}\}$: There is a monotone path $P=(w=z_{k-1},z_{k-2},\dots,z_0=r)$ such that if some $z_i=u_i$ then $z_j=u_j$ for each $j\in[0,i]$, and if some $z_i=v_i$ then $z_j=v_j$ for each $j\in[0,i]$. Observe that both $S':=(u_0,u_1,\dots,u_{k-1},u_k,z_{k-1},z_{k-2},\dots,z_1,z_0)$ and $S'':=(z_0,z_1,\dots,z_{k-1},v_k,v_{k-1},\dots,v_1,v_0)$ are lollipops. By assumption, $r_B(\overleftarrow{S})=\ell_B(S)>\frac{2}{3}|B|$. We have $r_B(S')>\frac{2}{3}|B|$ since $S'$ is a lollipop with $r_B(S')\geq r_B(S)$ and $\ell(S')<\ell(S)$. Similarly, $r_B(S'')>\frac{2}{3}|B|$. Hence $r_B(\overleftarrow{S})+r_B(S')+r_B(S'')>2|B|$. Thus $R_B(\overleftarrow{S})\cap R_B(S')\cap R_B(S'')\neq\emptyset$, which is a contradiction since $R_B(S')\cap R_B(S'')\subseteq R_B(S)=L_B(\overleftarrow{S})$. \emph{Case~1(e).} $w\in V_{k}$: This case is analogous to Case~1(d), except that here $P$ is a monotone path $(w=z_{k},z_{k-1},\dots,z_0=r)$, and $S':=(u_0,u_1,\dots,u_{k-1},u_k,z_{k},z_{k-1},\dots,z_1,z_0)$ and $S'':=(z_0,z_1,\dots,z_{k-1},z_{k},v_k,v_{k-1},\dots,v_1,v_0)$. \bigskip \emph{Case~2.} $S=(u_0,u_1,\dots,u_{k-1},u_k,u_{k+1},v_k,v_{k-1},\dots,v_1,v_0)$: Let $w$ be the vertex that forms a face $f=(u_k,w,u_{k+1})$ in clockwise order. Hence $w\in V_{k+1} \cup V_k$. \emph{Case~2(a).} $w\in V_{k+1}$: This case is analogous to Case~1(a) except that $S':=(u_0,u_1,\dots,u_{k-1},u_k,w,u_{k+1},v_k,v_{k-1},\dots,v_1,v_0)$. \emph{Case~2(b).} $w=v_k$: This case is analogous to Case~1(c) except with $S':=(u_0,u_1,\dots,u_{k-1},u_k,v_k,v_{k-1},\dots,v_1,v_0)$. \emph{Case~2(c).} $w\in V_{k}-\{v_k\}$: This case is analogous to Case~1(d), except that here $P$ is a monotone path $(w=z_{k},z_{k-1},\dots,z_0)$, and $S':=(u_0,u_1,\dots,u_{k-1},u_k,z_{k},z_{k-1},\dots,z_1,z_0)$ and $S'':=(z_0,z_1,\dots,z_{k-1},z_k,u_{k+1},v_k,v_{k-1},\dots,v_1,v_0)$. \bigskip Each case leads to a contradiction. Hence $r_B(S)\leq\frac{2}{3}|B|$ and $\ell_B(S)\leq\frac{2}{3}|B|$. Let $G_1$ be the subgraph induced by the vertices in $S$ and to the right of $S$. Let $G_2$ be the subgraph induced by the vertices in $S$ and to the left of $S$. By the Jordan Curve Theorem, no vertex to the right of $S$ is adjacent to a vertex to the left of $S$. Hence $G=G_1\cup G_2$ and $(G_1,G_2)$ is the desired separation. \end{proof} \end{document}