\documentclass[12pt]{article}
\usepackage{e-jc}
\usepackage[utf8]{inputenc}

\usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref}
\newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}}
\newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}}

\usepackage{amsthm}
\usepackage{amsfonts,amssymb}
\usepackage{amsmath}
\usepackage{colonequals}
\usepackage{lmodern}

\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}

\theoremstyle{definition}
\newtheorem{conjecture}[theorem]{Conjecture}

\newcommand{\sst}[2]{\left\{#1\,:\,#2\right\}}
\newcommand{\abs}[1]{\left\lvert#1\right\rvert}
\newcommand{\R}{\mathbf{R}}
\renewcommand{\le}{\leqslant}
\renewcommand{\ge}{\geqslant}
\renewcommand{\leq}{\leqslant}
\renewcommand{\geq}{\geqslant}


\title{\bf Fractional coloring of triangle-free planar graphs\thanks{This research was supported by the Czech-French Laboratory LEA STRUCO.}}
\author{Zdeněk Dvořák\thanks{Supported by the Center of Excellence -- Inst. for Theor. Comp. Sci., Prague, project P202/12/G061 of Czech Science Foundation.}\\
\small Computer Science Institute of Charles University\\[-0.8ex]
\small Prague, Czech Republic\\[-0.8ex]
\small\tt rakdver@iuuk.mff.cuni.cz\\
\and
Jean-Sébastien Sereni\thanks{This author's work was partially supported by the French \emph{Agence Nationale de la Recherche} under reference \textsc{anr 10 jcjc 0204 01}.}\\
\small Centre National de la Recherche Scientifique (LORIA)\\[-0.8ex]
\small Nancy, France\\[-0.8ex]
\small\tt sereni@kam.mff.cuni.cz\\
\and
Jan Volec\thanks{This author's work was supported by a grant of the French Government.}\\
\small Mathematics Institute and DIMAP\\[-0.8ex]
\small University of Warwick\\[-0.8ex]
\small Coventry, UK\\[-0.8ex]
\small\tt honza@ucw.cz
}
\date{\dateline{Feb 22, 2014}{??? ?, 2015}\\
\small Mathematics Subject Classifications: 05C15, 05C72}

\begin{document}
\maketitle

\begin{abstract}
We prove that every planar triangle-free graph on $n$ vertices has fractional chromatic number at most $3-\frac{3}{3n+1}$.
\end{abstract}

\section{Introduction} % (fold)
\label{sec:intro}
%
The interest in the chromatic properties of triangle-free planar graphs originated
with Grötzsch's theorem~\cite{grotzsch1959}, stating that such graphs are
$3$-colorable. Since then, several simpler proofs have been given, e.g.,~by
Thomassen~\cite{thom-torus,ThoShortlist}. Algorithmic questions have also been addressed: while most proofs
readily yield quadratic algorithms to $3$-color such graphs, it takes
considerably more effort to obtain asymptotically faster algorithms. Kowalik~\cite{Kow3col}
proposed an algorithm running in time $O(n\log n)$, which relies on the design of an
advanced data structure. More recently, Dvořák, Kawarabayashi and Thomas~\cite{DvoKawTho}
managed to obtain a linear-time algorithm, yielding at the same time a yet
simpler proof of Grötzsch's theorem.

The fact that all triangle-free planar graphs admit a $3$-coloring implies
that all such graphs have an independent set containing at least one third of
the vertices. Albertson, Bollobás and Tucker~\cite{AlbBolTuc} had conjectured that there is always a
larger independent set, which was confirmed by Steinberg and
Tovey~\cite{SteinbergTovey1993} even in a stronger sense:
all triangle-free planar $n$-vertex graphs admit a $3$-coloring where not all color classes
have the same size, and thus at least one of them forms an independent set of size
at least $\frac{n+1}{3}$.
This bound turns out to be tight for infinitely many triangle-free
graphs, as Jones~\cite{Jones1985} showed. As an aside, let us mention that
the graphs built by Jones have maximum degree $4$: this is no
coincidence as Heckman and Thomas later established that all triangle-free
planar $n$-vertex graphs with maximum degree at most $3$ have an independent
set of order at least $\frac{3n}{8}$, which again is a tight bound---actually
attained by planar graphs of girth $5$.

All these considerations naturally lead us to investigate the fractional
chromatic number $\chi_f$ of triangle-free planar graphs. Indeed,
this invariant is known to correspond to a weighted version of the
independence ratio. In addition, since $\chi_f(G)\le\chi(G)$ for every graph
$G$, Grötzsch's theorem implies that $\chi_f(G)\le3$ whenever $G$ is
triangle-free and planar.  On the other hand, Jones's construction shows the
existence of triangle-free planar graphs with fractional chromatic number
arbitrarily close to $3$.  Thus one wonders whether there exists a
triangle-free planar graph with fractional chromatic number exactly $3$. Let
us note that this happens for the circular chromatic number $\chi_c$, which is
a different relaxation of the ordinary chromatic number such that $\chi_f(G)\le
\chi_c(G)\le \chi(G)$ for every graph~$G$.

The purpose of this work is to answer this question. We do so by establishing
the following upper bound on the fractional chromatic number of
triangle-free planar $n$-vertex graphs, which depends on $n$.
\begin{theorem}\label{thm-main}
Every planar triangle-free graph on $n$ vertices has fractional chromatic
number at most $\frac{9n}{3n+1}=3-\frac{3}{3n+1}$.
\end{theorem}

A consequence of Theorem~\ref{thm-main} is that no (finite) triangle-free
planar graph has fractional chromatic number equal to $3$.  How much is it
possible to improve the bound of Theorem~\ref{thm-main}?  The aforementioned
construction of Jones~\cite{Jones1985} yields, for each $n\ge 2$ such that
$n\equiv 2\pmod 3$, a triangle-free planar graph $G_n$ with
$\alpha(G_n)=\frac{n+1}{3}$.  Consequently, $\chi_f(G_n)\ge
\frac{3n}{n+1}=3-\frac{3}{n+1}$.  Therefore, the bound of form $3-\frac{c}{n}$
for some $c$ in Theorem~\ref{thm-main} is qualitatively the best possible.

The bound can be improved for triangle-free planar graphs with maximum degree at most four,
giving an exact result for such graphs.
%
\begin{theorem}\label{thm-main4}
Every planar triangle-free $n$-vertex graph of maximum degree at most four
has fractional chromatic number at most $\frac{3n}{n+1}$.
\end{theorem}

Furthermore, the graphs of Jones's construction contain a large number of separating 4-cycles
(actually, all their faces have length five).  We show that planar triangle-free graphs
of \emph{maximum degree $4$} and \emph{without separating $4$-cycles} cannot have fractional
chromatic number arbitrarily close to $3$.

\begin{theorem}\label{thm-main4nos}
There exists $\delta>0$ such that every planar triangle-free graph of maximum degree at most four
and without separating $4$-cycles has fractional chromatic number at most $3-\delta$.
\end{theorem}

Dvořák and Mnich~\cite{dmnich} proved that there exists $\beta>0$ such that all planar triangle-free
$n$-vertex graphs without separating $4$-cycles contain an independent set of size at least $n/(3-\beta)$.
This gives evidence that the restriction on the maximum degree in Theorem~\ref{thm-main4nos} might not
be necessary.

\begin{conjecture}\label{conj-h}
There exists $\delta>0$ such that every planar triangle-free graph without separating $4$-cycles has
fractional chromatic number at most $3-\delta$.
\end{conjecture}

Faces of length four are usually easy to deal with in the proofs by collapsing; thus the following
seemingly simpler variant of Conjecture~\ref{conj-h} is likely to be equivalent to it.

\begin{conjecture}[Dvořák and Mnich~\cite{dmnich}]
There exists $\delta>0$ such that every planar graph of girth at least five has
fractional chromatic number at most $3-\delta$.
\end{conjecture}

%
% section Introduction (end)
\section{Notation and auxiliary results} % (fold)
\label{sec:note}
%
Consider a graph $G$.  For an integer $a\ge 1$, let $[a]=\{1,\ldots,a\}$.  An
\emph{$a$-fractional coloring} of $G$ is a function $\varphi$ assigning to
each vertex of $G$ a subset of $[a]$, such that $\varphi(u)\cap
\varphi(v)=\emptyset$ for all edges $uv$ of $G$.  Let $f\colon V(G)\to [a]$ be
any function.  If the $a$-fractional coloring $\varphi$ satisfies
$|\varphi(v)|\ge f(v)$ for every $v\in V(G)$, then $\varphi$ is an
\emph{$(a,f)$-coloring} of~$G$.  If $|\varphi(v)|=f(v)$ for every $v\in V(G)$,
then the $(a,f)$-coloring $\varphi$ is \emph{tight}.  Note that if $G$ has an
$(a,f)$-coloring, then it also has a tight one.  If $f$ is the constant
function assigning to each vertex of $G$ the value $b\in[a]$, then an
$(a,f)$-coloring is said to be an \emph{$(a:b)$-coloring}.  An
\emph{$a$-coloring} is an $(a:1)$-coloring.

Let $f_1\colon V(G)\to [a_1]$ and $f_2\colon V(G)\to [a_2]$ be arbitrary functions, and
let $f\colon V(G)\to [a_1+a_2]$ be defined by $f(v)=f_1(v)+f_2(v)$ for all $v\in V(G)$.
Suppose that $\varphi_i$ is an $(a_i,f_i)$-coloring of $G$ for $i\in\{1,2\}$.
Let $\varphi$ be defined by setting $\varphi(v)=\varphi_1(v)\cup \sst{a_1+c}{c\in\varphi_2(v)}$
for every $v\in V(G)$.  Then $\varphi$ is an $(a_1+a_2,f)$-coloring of $G$, and we write
$\varphi=\varphi_1+\varphi_2$.  For an integer $k\ge 1$, we define $k\varphi$
to be $\underbrace{\varphi+\cdots+\varphi}_{\text{$k$ times}}$.

The fractional chromatic number of a graph can be expressed in various equivalent
ways, see~\cite{ScheinermanUllman2011} for details.  In this paper, we use the following
definition.  The \emph{fractional chromatic number} of $G$ is
\[
\chi_f(G)=\inf \sst{\frac{a}{b}}{\text{$G$ has an $(a:b)$-coloring}}.
\]

We need several results related to Grötzsch's theorem.
The following lemma was proved for vertices of degree at most three by
Steinberg and Tovey~\cite{SteinbergTovey1993}.
The proof for vertices of degree four follows from the results of Dvořák and Lidický~\cite{col8cyc},
as observed by Dvořák, Král' and Thomas~\cite{trfree5}.
%
\begin{lemma}\label{lemma-tovey}
If $G$ is a triangle-free planar graph and $v$ is a vertex of $G$ of degree at most four,
then there exists a $3$-coloring of $G$ such that all neighbors of $v$ have the same color.
\end{lemma}
\noindent In fact, Dvořák, Král' and Thomas~\cite{trfree5} proved the following stronger statement.
\begin{lemma}\label{lemma-far}
There exists an integer $D\ge 4$ with the following property.
Let $G$ be a triangle-free planar graph without separating $4$-cycles and
let $X$ be a set of vertices of $G$ of degree at most four.  If the distance between every two vertices in $X$ is at least $D$,
then there exists a $3$-coloring of $G$ such that all neighbors of vertices of $X$ have the same color.
\end{lemma}

Let $G$ be a triangle-free plane graph.  A $5$-face $f=v_1v_2v_3v_4v_5$ of $G$ is \emph{safe}
if $v_1$, $v_2$, $v_3$ and $v_4$ have degree exactly three, their
neighbors $x_1, \ldots, x_4$ (respectively) not incident with $f$ are
pairwise distinct and non-adjacent, and
\begin{itemize}
\item the distance between $x_2$ and $v_5$ in $G-\{v_1,v_2,v_3,v_4\}$
is at least four, and
\item $G-\{v_1,v_2,v_3,v_4\}$ contains no path of length exactly
three between $x_3$ and $x_4$.
\end{itemize}

\begin{lemma}[Dvořák, Kawarabayashi and Thomas~{\cite[Lemma~2.2]{DvoKawTho}}]\label{lemma-safe}
If $G$ is a plane triangle-free graph of minimum degree at least three
and all faces of $G$ have length five, then $G$ has a safe face.
\end{lemma}

Finally, let us recall the folding lemma, which is frequently used in the
coloring theory of planar graphs.

\begin{lemma}[Klostermeyer and Zhang~\cite{KloZhang}]\label{lemma-folding}
Let $G$ be a planar graph with odd-girth at least $g>3$.
If $C=v_0v_1\dots v_{r-1}$ is a facial circuit of $G$ with $r\ne g$,
then there is an integer $i\in\{0,\ldots,r-1\}$ such that
the graph $G'$ obtained from $G$ by identifying $v_{i-1}$ and $v_{i+1}$
(where indices are taken modulo $r$) is also of odd-girth at least $g$.
\end{lemma}

\section{Proofs}

First, let us show a lemma based on the idea of Hilton \emph{et. al.}~\cite{planfr5}.

\begin{lemma}\label{lemma-wtone}
Let $G$ be a planar triangle-free graph.  For a vertex $v\in V(G)$, let $f_v\colon V(G)\to[3]$ be defined by $f_v(v)=2$
and $f_v(w)=1$ for $w\in V(G)\setminus \{v\}$.
If $v$ has degree at most $4$, then $G$ has a $(3,f_v)$-coloring.
\end{lemma}
\begin{proof}
Lemma~\ref{lemma-tovey} implies that there exists a $3$-coloring of $G$ such that all neighbors of $v$ have the
same color, without loss of generality the color $\{1\}$.  Hence, we can color $v$ by the set $\{2,3\}$.
\end{proof}

Theorem~\ref{thm-main4} now readily follows.
%
\begin{proof}[Proof of Theorem~\ref{thm-main4}]
   Let $V(G)=\{v_1, \ldots, v_n\}$.  For $i\in\{1,\ldots, n\}$, let $f_{v_i}\colon V(G)\to [3]$ be defined as in Lemma~\ref{lemma-wtone},
and let $\varphi_i$ be a $(3,f_{v_i})$-coloring of $G$. Then $\varphi_1+\cdots+\varphi_n$ is a $(3n:n+1)$-coloring of $G$.
\end{proof}

Similarly, Lemma~\ref{lemma-far} implies Theorem~\ref{thm-main4nos}.
%
\begin{proof}[Proof of Theorem~\ref{thm-main4nos}]
Let $D$ be the constant of Lemma~\ref{lemma-far}, let $m=4^D$ and let
$\delta=\frac{3}{m+1}$.  We show that every planar triangle-free graph $G$ of
maximum degree at most four and without separating $4$-cycles has a
$(3m:m+1)$-coloring, and thus $\chi_f(G)\le \frac{3m}{m+1}=3-\delta$.

Let $G'$ be the graph obtained from $G$ by adding edges between all pairs of
vertices at distance at most $D-1$.  The maximum degree of $G'$ is less than
$4^D=m$, and thus $G'$ has a coloring by at most $m$ colors.  Let $C_1$,
\ldots, $C_m$ be the color classes of this coloring (some may be empty).  For
$i\in [m]$, let $f_i$ be the function defined by $f_i(v)=2$ for $v\in C_i$ and
$f_i(v)=1$ for $v\in V(G)\setminus C_i$.  Note that the distance in $G$
between any distinct vertices in $C_i$ is at least $D$, and thus
Lemma~\ref{lemma-far} ensures that $G$ has a $(3,f_i)$-coloring $\varphi_i$.
Then $\varphi_1+\cdots+\varphi_m$ is a $(3m:m+1)$-coloring of $G$.
\end{proof}

The proof of Theorem~\ref{thm-main} is somewhat more involved.  Let $G$ be a
plane triangle-free graph.  We say that $G$ is a \emph{counterexample} if
there exists an integer $n\ge |V(G)|$ such that $G$ does not have a
$(9n:3n+1)$-coloring.  We say that $G$ is a \emph{minimal counterexample} if
$G$ is a counterexample and no plane triangle-free graph with fewer than
$|V(G)|$ vertices is a counterexample.  Observe that every minimal
counterexample is connected.
%
\begin{lemma}\label{lemma-mindeg2}
If $G$ is a minimal counterexample, then $G$ is $2$-connected.  Consequently, the minimum degree of $G$ is at least two.
\end{lemma}
\begin{proof}
Let $n\ge |V(G)|$ be an integer such that $G$ does not have a $(9n:3n+1)$-coloring.
Since $9n>2(3n+1)$, it follows that $G$ has at least three vertices.
Hence, it suffices to prove that $G$ is $2$-connected, and the bound on the minimum degree will follow.

Suppose for a contradiction that $G$ is not $2$-connected, and let $G_1$ and $G_2$ be subgraphs of
$G$ such that $G=G_1\cup G_2$, the graph $G_1$ intersects $G_2$ in exactly one
vertex $v$, and $|V(G_1)|,|V(G_2)|<|V(G)|$.
By the minimality of $G$, neither $G_1$ nor $G_2$ is a counterexample, and thus for $i\in\{1,2\}$,
there exists a $(9n:3n+1)$-coloring $\varphi_i$ of $G_i$.  By permuting the colors, we can assume
that $\varphi_1(v)=\varphi_2(v)$.  Hence, $\varphi_1\cup\varphi_2$ is a $(9n:3n+1)$-coloring of $G$,
which is a contradiction.
\end{proof}

\begin{lemma}\label{lemma-faces}
If $G$ is a minimal counterexample, then every face of $G$ has length exactly~$5$.
\end{lemma}
\begin{proof}
Let $n\ge |V(G)|$ be an integer such that $G$ does not have a $(9n:3n+1)$-coloring.
Suppose for a contradiction that $G$ has a face $f$ of length other than $5$.  Since $G$ is triangle-free, it has odd girth
at least five, and by Lemma~\ref{lemma-folding}, there exists a path $v_1v_2v_3$ in the boundary of $f$
such that the graph $G'$ obtained by identifying $v_1$ with $v_3$ to a single vertex $z$ has odd girth at least five as well.
It follows that $G'$ is triangle-free.  Since $G$ is a minimal counterexample, $G'$ has a $(9n:3n+1)$-coloring,
and by giving both $v_1$ and $v_3$ the color of $z$, we obtain a $(9n:3n+1)$-coloring of $G$.
This is a contradiction.
\end{proof}

\begin{lemma}\label{lemma-mindeg3}
If $G$ is a minimal counterexample, then $G$ has minimum degree at least three.
\end{lemma}
\begin{proof}
Let $n\ge |V(G)|$ be an integer such that $G$ does not have a $(9n:3n+1)$-coloring.
By Lemma~\ref{lemma-mindeg2}, the graph $G$ has minimum degree at
least two.  Suppose for a contradiction that $v\in V(G)$ has degree two.  Let $f_v$ be defined as in Lemma~\ref{lemma-wtone}
and let $\varphi_1$ be a $(3,f_v)$-coloring of $G$.

Since $G$ is a minimal counterexample and $|V(G-v)|\le n-1$, there exists a tight
$(9n-9:3n-2)$-coloring $\varphi_2$ of $G-v$. Let $f(x)=3n-2$ for $x\in V(G-v)$ and $f(v)=3n-5$.
Since both neighbors of $v$ are assigned sets of $3n-2$ colors, there are at least $(9n-9)-2(3n-2)=3n-5$
colors not appearing at any neighbor of $v$, and thus $\varphi_2$ can be extended to a $(9n:f)$-coloring of $G$.

However, $3\varphi_1+\varphi_2$ is a $(9n:3n+1)$-coloring of $G$, which is a contradiction.
\end{proof}

\begin{lemma}\label{lemma-nosafe}
No minimal counterexample contains a safe $5$-face.
\end{lemma}
\begin{proof}
Let $G$ be a minimal counterexample.  Let $n\ge |V(G)|$ be an integer such that $G$ does not have a $(9n:3n+1)$-coloring.
Suppose for a contradiction that $f$ contains a safe $5$-face
$f=v_1v_2v_3v_4v_5$, and let $x_1, \dots, x_4$ be the neighbors of $v_1,
\ldots, v_4$ that are not incident with $f$, respectively.
For $i\in\{1,\ldots,4\}$, let $f_{v_i}$ be defined as in Lemma~\ref{lemma-wtone} and let
$\varphi_i$ be a $(3,f_{v_i})$-coloring of $G$.

Let $G'$ be the plane graph obtained from $G-\{v_1,v_2,v_3,v_4\}$ by
identifying $x_2$ with $v_5$ into a new vertex $u_1$, and $x_3$ with $x_4$
into a new vertex $u_2$.  Since $f$ is safe, $G'$ is triangle-free.  Let
$N=9n-54$.  Since $G$ is a minimal counterexample and $|V(G')|\le n-6$, we
conclude that $G'$ has a tight $(N:3n-17)$-coloring $\varphi_5$.  Let
$f(x)=3n-17$ for $x\in V(G-\{v_1,v_2,v_3,v_4\})$ and $f(v_i)=3n-20$ for
$i\in\{1,\ldots,4\}$.  We extend $\varphi_5$ to an $(N,f)$-coloring of $G$ as
follows.

Let $\varphi_5(x_2)=\varphi_5(v_5)=\varphi_5(u_1)$ and $\varphi_5(x_3)=\varphi_5(x_4)=\varphi_5(u_2)$.
Note that $|\varphi_5(x_1)\cup \varphi_5(v_5)|\le 2(3n-17)$, and thus we can choose
$\varphi_5(v_1)$ as a subset of $[N]\setminus (\varphi_5(x_1)\cup \varphi_5(v_5))$ of size
$3n-20$.  Similarly, choose $\varphi_5(v_2)$ as a subset of $[N]\setminus (\varphi_5(x_2)\cup
\varphi_5(v_1))$ of size $3n-20$.  Let $M_3=[N]\setminus (\varphi_5(v_2)\cup \varphi_5(x_3))$ and
$M_4=[N]\setminus (\varphi_5(v_5)\cup \varphi_5(x_4))$.  Note that
$|M_3|\ge 3n-20$ and $|M_4|\ge 3n-20$.  Furthermore, since
$\varphi_5(x_3)=\varphi_5(x_4)$ and $\varphi_5(v_2)\cap \varphi_5(v_5)=\varphi_5(v_2)\cap \varphi_5(x_2)=\emptyset$, we have
$|M_3\cup M_4|=N-|\varphi_5(x_3)|=N-(3n-17) > 2(3n-20)$.
Let $\varphi_5(v_3)\subseteq M_3$ be a set of size $3n-20$ chosen so that $|\varphi_5(v_3)\cap M_4|$ is minimum.
Observe that $|M_4\setminus \varphi_5(v_3)|\ge 3n-20$, and thus we can choose a set
$\varphi_5(v_4)\subseteq M_4\setminus \varphi_5(v_3)$ of size $3n-20$.  This gives an $(N,f)$-coloring of $G$.

Also, by Grötzsch's theorem, $G$ has a $(3:1)$-coloring $\varphi_6$.
However, $3(\varphi_1+\varphi_2+\varphi_3+\varphi_4)+\varphi_5+6\varphi_6$ is a $(9n:3n+1)$-coloring of $G$, which is a contradiction.
\end{proof}

We can now establish Theorem~\ref{thm-main}.
%
\begin{proof}[Proof of Theorem~\ref{thm-main}]
Suppose for a contradiction that there exists a planar triangle-free graph $G$ on $n$ vertices with fractional chromatic
number greater than $3-\frac{3}{3n+1}$.  Then $G$ has no $(9n:3n+1)$-coloring,
and thus $G$ is a counterexample.  Therefore, there exists a minimal
counterexample $G_0$. Lemmas~\ref{lemma-mindeg3}, \ref{lemma-faces} and
\ref{lemma-safe} imply that $G_0$ has a safe $5$-face.  However, that contradicts
Lemma~\ref{lemma-nosafe}.
\end{proof}

\begin{thebibliography}{10}
\bibitem{AlbBolTuc}
M.~Albertson, B.~Bollob\'as, and S.~Tucker.
\newblock The independence ratio and the maximum degree of a graph.
\newblock {\em Congr. Numer.}, 17:43--50, 1976.

\bibitem{DvoKawTho}
Z.~Dvo\v{r}\'ak, K.~Kawarabayashi, and R.~Thomas.
\newblock Three-coloring triangle-free planar graphs in linear time.
\newblock {\em Trans. on Algorithms}, 7:article no. 41, 2011.

\bibitem{trfree5}
Z.~Dvo\v{r}\'ak, D.~Kr\'al', and R.~Thomas.
\newblock Three-coloring triangle-free graphs on surfaces {V}. {C}oloring
  planar graphs with distant anomalies.
\newblock \arxiv{0911.0885v2}, January 2015.

\bibitem{col8cyc}
Z.~Dvo\v{r}\'ak and B.~Lidick\'y.
\newblock 3-coloring triangle-free planar graphs with a precolored 8-cycle.
\newblock {\em J. Graph Theory}, forthcoming.

\bibitem{dmnich}
Z.~Dvo\v{r}\'ak and M.~{Mnich}.
\newblock {Large independent sets in triangle-free planar graphs}.
\newblock \arxiv{1311.2749}, November 2013.

\bibitem{grotzsch1959}
H.~Gr{\"o}tzsch.
\newblock Ein {D}reifarbensatz f\"{u}r {D}reikreisfreie {N}etze auf der
  {K}ugel.
\newblock {\em Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg. Math.-Nat.
Reihe}, 8:109--120, 1958/1959.

\bibitem{planfr5}
A.~Hilton, R.~Rado, and S.~Scott.
\newblock A $(<5)$-colour theorem for planar graphs.
\newblock {\em Bull. London Math. Soc.}, 5:302--306, 1973.

\bibitem{Jones1985}
K.~F.~Jones.
\newblock Minimum independence graphs with maximum degree four.
\newblock In {\em Graphs and Applications ({B}oulder, {C}olo., 1982)},
  Wiley-Intersci. Publ., pages 221--230. Wiley, 1985.

\bibitem{KloZhang}
W.~Klostermeyer and C.~Q.~Zhang.
\newblock $(2+\epsilon)$-coloring of planar graphs with large odd-girth.
\newblock {\em J. Graph Theory}, 33:109--119, 2000.

\bibitem{Kow3col}
\L.~Kowalik.
\newblock Fast 3-coloring triangle-free planar graphs.
\newblock In Susanne Albers and Tomasz Radzik, editors, {\em ESA}, volume 3221
  of {\em Lecture Notes in Computer Science}, pages 436--447. Springer, 2004.

\bibitem{ScheinermanUllman2011}
E.~R.~Scheinerman and D.~H.~Ullman.
\newblock {\em Fractional Graph Theory}.
\newblock Dover Publications Inc., Mineola, NY, 2011.

\bibitem{SteinbergTovey1993}
R.~Steinberg and C.~A.~Tovey.
\newblock Planar {R}amsey numbers.
\newblock {\em J. Combin. Theory, Ser.~B}, 59(2):288--296, 1993.

\bibitem{thom-torus}
C.~Thomassen.
\newblock Gr{\"o}tzsch's 3-color theorem and its counterparts for the torus and
  the projective plane.
\newblock {\em J. Combin. Theory, Ser.~B}, 62:268--279, 1994.

\bibitem{ThoShortlist}
C.~Thomassen.
\newblock A short list color proof of {G}r{\"o}tzsch's theorem.
\newblock {\em J. Combin. Theory, Ser.~B}, 88:189--192, 2003.
\end{thebibliography}
\end{document}