\documentclass[12pt]{article}
\usepackage{e-jc}
\specs{P2.46}{25(2)}{2018}


\usepackage{amsfonts}
\usepackage{tikz}

\usepackage{amsthm,amsmath,amssymb}
\usepackage{graphicx}
\usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref}

\dateline{Sep 14, 2017}{May 30, 2018}{Jun 8, 2018}
\MSC{05C10, 05C15}

\Copyright{  The authors. Released under the CC BY-ND license (International 4.0).}

\title{A note on non-4-list colorable planar graphs}

\author{Arnfried Kemnitz
\\
{\small Technical University Braunschweig}\\[-0.8ex]
\small Braunschweig, Germany\\
{\small\tt a.kemnitz@tu-bs.de}\\
\and
Margit Voigt\\
\small University of the Applied Sciences\\[-0.8ex]
\small Dresden, Germany\\
\small\tt mvoigt@informatik.htw-dresden.de
}

% use these commands for typesetting doi and arXiv references in the bibliography
%\newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}}
%\newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}}

% all overfull boxes must be fixed;
% i.e. there must be no text protruding into the margins


% declare theorem-like environments

%\newtheorem{claim}[theorem]{Claim}
%\newtheorem{corollary}[theorem]{Corollary}

%\newtheorem{problem}[theorem]{Problem}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% if needed include a line break (\\) at an appropriate place in the title



% input author, affilliation, address and support information as follows;
% the address should include the country, and does not have to include
% the street address



% \date{\dateline{submission date}{acceptance date}\\
% \small Mathematics Subject Classifications: comma separated list of
% MSC codes available from http://www.ams.org/mathscinet/freeTools.html}


\begin{document}

\maketitle

\def \chis {\chi_{sc}}
\def \Ra {\Rightarrow}
\newcommand{\Nn}{\mathbb N}
\def \ra {\rightarrow}

%\DeclareMathOperator{\size}{size}





\begin{abstract}
The Four Color Theorem states that every planar graph is properly 4-colorable. Moreover, it is well known that there are planar graphs that are non-$4$-list colorable. In this paper we investigate a problem combining proper colorings and list colorings. We ask whether the vertex set of every planar graph can be partitioned into two subsets where one subset induces a bipartite graph and the other subset induces a $2$-list colorable graph. We answer this question in the negative strengthening the result on non-$4$-list colorable planar graphs.

%\bigskip\noindent \textbf{Keywords:} planar graphs, list coloring, partition
\end{abstract}


Let $G=(V,E)$ be a simple graph and for every vertex $v\in V$ let $L(v)$ be a
set (list) of available colors. A \emph{ $k$-assignment} is a list assignment with $|L(v)|=k$ for all
$v\in V(G)$.
A graph $G$ is called \emph{ $L$-colorable} if there is a proper coloring $c$ of the vertices
with $c(v)\in L(v)$ for all $v\in V(G)$ and $c(v)\not=c(w)$ for all edges
$vw\in E(G)$.
If $G$ is $L$-colorable for all possible $k$-assignments then $G$ is called
\emph{ $k$-list colorable}.


In this note we consider simple planar graphs.
Since 1993 it is known by Thomassen~\cite{Thom94} and Voigt~\cite{Voig93} that every planar graph is
5-list colorable but there are planar graphs that are non-$4$-list
colorable.


Recently, Choi and Kwon~\cite{Choi} introduced the concept of a \emph{
  $t$-common $k$-assignment} which is a $k$-assignment satisfying $|\bigcap_{v\in
  V(G)} L(v)|\geq t$.
Using the Four Color Theorem~\cite{AppelH89,RobSST96a}, it is easy to see that every planar graph is
$L$-colorable for every $3$-common $4$-assignment $L$. Moreover, Choi and Kwon~\cite{Choi}
constructed a planar graph $G$ with a $1$-common $4$-assignment $L$ such that
$G$ is not $L$-colorable and they explicitly asked the following problem.

\begin{problem} \label{p1} Is every planar graph $L$-colorable for
  every $2$-common $4$-assignment $L$?
\end{problem}

Since every proper coloring of the vertices gives a partition of the vertex set we
may look for the problem from another point of view.

\begin{problem}
Let $G$ be a  planar graph. Is it possible to partition the vertex set of $G$
into two sets in such a way that one partition set induces a bipartite graph
and the other one induces a $2$-list colorable graph?
\end{problem}

If such a partition would always exist for planar graphs, then it would strengthen  the
Four Color Theorem. Moreover, we have the following relationship to
Problem~\ref{p1}.

\begin{claim}
If the vertex set $V$ of a  planar graph $G$ can be partitioned into
$V_1$ and $V_2$ such that $V_1$ induces a bipartite graph and $V_2$ induces a
$2$-list colorable graph then $G$ is $L$-colorable for every $2$-common
$4$-assignment $L$.
\end{claim}

\begin{proof} Let $G$ be a  planar graph and $L$ be a $2$-common $4$-assignment
for the vertices of $G$ with $\{\alpha,\beta\}\subseteq L(v)$ for all $v\in
V(G)$. Properly color the subgraph induced by $V_1$ with $\alpha$ and $\beta$
and set $L'(v)=L(v)\setminus \{\alpha,\beta\}$ for all $v\in V_2$. Since the
subgraph induced by $V_2$ is $2$-list colorable it can be colored from the
remaining lists $L'(v)$. \end{proof}


Since every acyclic graph is $2$-list colorable we may put a stronger question
for the partition of $G$.

\begin{problem} Let $G$ be a  planar graph. Is it possible to partition the
  vertex set $V$ into $V_1$ and  $V_2$ such that the subgraph induced by $V_1$ is a
  bipartite graph and the subgraph induced by $V_2$ is a forest?
\end{problem}

Unfortunately, this is not possible for every planar graph as shown by Wegner
in 1973~\cite{Weg}.



\begin{theorem}
There is a planar graph $G$ such that in every proper $4$-coloring of $G$ the
vertices of every two color classes induce a subgraph containing a cycle.
\end{theorem}



\begin{figure}[h]\label{f1} \begin{center}
%\input{g1-ohne.tex}
\begin{tikzpicture}[scale=0.4]

\def \1 {(1.5,1.0)}
\def \2 {(13.5,1.0)}
\def \3 {(7.5,2.0)}
\def \4 {(5.5,3.0)}
\def \5 {(9.0,3.0)}
\def \6 {(10.0,4.0)}
\def \7 {(7.5,5.5)}
\def \8 {(6.5,7.5)}
\def \9 {(8.5,7.5)}
\def \a {(7.5,11.5)}
\newcommand \knoten[1] {\draw[fill] #1 circle [radius=0.05];}
%\draw[fill] \1 circle [radius=0.05];%1
%\draw[fill] \1 circle [radius=0.05];
\knoten{\1}
\knoten{\2}
\knoten{\3}
\knoten{\4}
\knoten{\5}
\knoten{\6}
\knoten{\7}
\knoten{\8}
\knoten{\9}
\knoten{\a}
\draw \1 --\2 --\3 --\1 ;
\draw \1 --\4 --\3 --\5 --\2 --\6 --\5 --\4 --\1 ;
\draw \1 --\8 --\4 --\7 --\5 ;
\draw \8 -- \7 --\6  --\9 --\7 ;
\draw \8 --\9 --\2 --\a -- \1 ;
\draw \8 --\a --\9 ;
\node[below] at \1 {$v_1$};
\node[below] at \2 {$v_2$};
\node[below] at \3 {$v_3$};
\node[below] at \4 {$v_4$};
\node[below] at \5 {$v_5$};
\node[left] at \6 {$v_6$};
\node[left] at \7 {$v_7$};
\node[left] at \8 {$v_8$};
\node[right] at \9 {$v_9$};
\node[above] at \a {$v_{10}$};
\node[] at (4.5,3.5) {$D_1$};
\node[] at (10.0,3.2) {$D_2$};

\knoten{(1.0,5.0)}
\node[below] at (1.0,5.0) {$v_1$};
\knoten{(1.0,13.0)}
\node[above] at (1.0,13.0) {$v_8$};
\knoten{(4.0,9.0)}
\node[right] at (4.0,9.0) {$v_4$};
\knoten{(2.5,8.0)}
%\node[left] at (2.5,8.0) {$a$};
\knoten{(1.5,9.0)}
%\node[left] at (1.5,9.0) {$b$};
\knoten{(2.5,10.0)}
%\node[left] at (2.5,10.0) {$c$};
\draw (1.0,5.0)--(1.0,13)--(4.0,9.0)--(1.0,5.0)--(2.5,8.0)--(4.0,9.0)--(2.5,10.0)--(1.0,13.0)--(1.5,9.0)--(1.0,5.0);
\draw (2.5,8.0)--(1.5,9.0)--(2.5,10.0)--(2.5,8.0);
\node at (3.0,13.0) {$D_1$};

\knoten{(14.0,5.0)}
\node[below] at (14.0,5.0) {$v_2$};
\knoten{(14.0,13.0)}
\node[above] at (14.0,13.0) {$v_6$};
\knoten{(11.0,9.0)}
\node[left] at (11.0,9.0) {$v_5$};
\knoten{(12.5,8.0)}
%\node[right] at (12.5,8.0) {$a$};
\knoten{(13.5,9.0)}
%\node[right] at (13.5,9.0) {$b$};
\knoten{(12.5,10.0)}
%\node[right] at (12.5,10.0) {$c$};
\draw (14.0,5.0)--(14.0,13)--(11.0,9.0)--(14.0,5.0)--(12.5,8.0)--(11.0,9.0)--(12.5,10.0)--(14.0,13.0)--(13.5,9.0)--(14.0,5.0);
\draw (12.5,8.0)--(13.5,9.0)--(12.5,10.0)--(12.5,8.0);
\node at (12.0,13.0) {$D_2$};
\end{tikzpicture}
 \end{center}
\caption{Subgraph $G_1$ of $G$}
\end{figure}

The construction of Wegner does not give an answer to Problem
\ref{p1} but based on his construction, we were able to find our construction.

\begin{theorem} There is a  planar graph $G$ and a $2$-common $4$-assignment $L$
such that $G$ is not $L$-colorable.
\end{theorem}


\begin{proof}
We will construct a planar graph $G$ and a $2$-common
$4$-assignment $L$ in two steps.
In the first step we consider the subgraph $G_1$ of $G$, which is shown in
Figure~1. The structures inside the triangles $D_1$ and $D_2$ are depicted
separately outside.

\begin{figure}[h] \label{f2} \begin{center}
%\input{g1-mit.tex}
\begin{tikzpicture}[scale=0.8]
%\draw[fill] \1 circle [radius=0.05];%1
%\draw[fill] \1 circle [radius=0.05];
\def \1 {(1.5,1.0)}
\def \2 {(13.5,1.0)}
\def \3 {(7.5,2.0)}
\def \4 {(5.5,3.0)}
\def \5 {(9.0,3.0)}
\def \6 {(10.0,4.0)}
\def \7 {(7.5,5.5)}
\def \8 {(6.5,7.5)}
\def \9 {(8.5,7.5)}
\def \a {(7.5,11.5)}
\newcommand \knoten[1] {\draw[fill] #1 circle [radius=0.05];}

\knoten{\1}
\knoten{\2}
\knoten{\3}
\knoten{\4}
\knoten{\5}
\knoten{\6}
\knoten{\7}
\knoten{\8}
\knoten{\9}
\knoten{\a}
\draw \1 --\2 --\3 --\1 ;
\draw \1 --\4 --\3 --\5 --\2 --\6 --\5 --\4 --\1 ;
\draw \1 --\8 --\4 --\7 --\5 ;
\draw \8 -- \7 --\6  --\9 --\7 ;
\draw \8 --\9 --\2 --\a -- \1 ;
\draw \8 --\a --\9 ;
\node[below] at \1 {$1$};
\node[below] at \2 {$2$};
\node[below] at \3 {\small $1,2,\alpha,\beta$};
\node[below] at \4 {\small$1,3,\alpha,\beta$};
\node[below] at \5 {\small$2,3,\alpha,\beta$};
\node[right] at \6 {\small$2,4,\alpha,\beta$};
\node[left] at \7 {\small$3,4,\alpha,\beta$};
\node[left] at \8 {\small$1,4,\alpha,\beta$};
\node[right] at \9 {\small$2,4,\alpha,\beta$};
\node[above] at \a {\small$1,2,\alpha,\beta$};
\node[] at (4.5,3.5) {$D_1$};
\node[] at (10.0,3.2) {$D_2$};

\knoten{(1.0,5.0)}
\node[below] at (1.0,5.0) {\small$1$};
\knoten{(1.0,13.0)}
\node[above] at (1.0,13.0) {\small$1,{4},\alpha,\beta$};
\knoten{(4.0,9.0)}
\node at (4.0,9.0) {\small$1,{3},\alpha,\beta$};
\knoten{(2.5,8.0)}
\node[] at (2.5,8.0) {\small$1,3,\alpha,\beta$};
\knoten{(1.5,9.0)}
\node[] at (1.5,9.0) {\small$1,4,\alpha,\beta$};
\knoten{(2.5,10.0)}
\node[] at (2.5,10.0) {\small$3,4,\alpha,\beta$};
\draw (1.0,5.0)--(1.0,13)--(4.0,9.0)--(1.0,5.0)--(2.5,8.0)--(4.0,9.0)--(2.5,10.0)--(1.0,13.0)--(1.5,9.0)--(1.0,5.0);
\draw (2.5,8.0)--(1.5,9.0)--(2.5,10.0)--(2.5,8.0);
\node at (3.0,13.0) {$D_1$};

\knoten{(14.0,5.0)}
\node[below] at (14.0,5.0) {\small$2$};
\knoten{(14.0,13.0)}
\node[above] at (14.0,13.0) {\small$2,4,\alpha,\beta$};
\knoten{(11.0,9.0)}
\node[] at (11.0,9.0) {\small$2,3,\alpha,\beta$};
\knoten{(12.5,8.0)}
\node[] at (12.5,8.0) {\small$2,3,\alpha,\beta$};
\knoten{(13.5,9.0)}
\node[] at (13.5,9.0) {\small$2,4,\alpha,\beta$};
\knoten{(12.5,10.0)}
\node[] at (12.5,10.0) {\small$3,4,\alpha,\beta$};
\draw (14.0,5.0)--(14.0,13)--(11.0,9.0)--(14.0,5.0)--(12.5,8.0)--(11.0,9.0)--(12.5,10.0)--(14.0,13.0)--(13.5,9.0)--(14.0,5.0);
\draw (12.5,8.0)--(13.5,9.0)--(12.5,10.0)--(12.5,8.0);
\node at (12.0,13.0) {$D_2$};
\end{tikzpicture}
\end{center}
\caption{Subgraph $G_1$ with a 2-common 4-list assignment and two precolored vertices}
\end{figure}




Let $v_1$ be precolored by $1$ and $v_2$ be precolored by $2$, and consider the
list assignment for the other vertices of $G_1$ given in Figure~2.
Assume that there is a proper coloring $c$ that assigns every vertex $v$ a color
$c(v)\in L(v)$ such that adjacent vertices get different colors.




At first, let $v_{10}$ be colored by $\alpha$.
Clearly, one of the vertices $v_4$ and $v_5$ must be colored by $3$ since
otherwise $v_3$ would not be colorable.
\begin{itemize}
\item Case 1: $c(v_4)=3$

Since $c(v_5)\in\{\alpha,\beta\}$ and
$\{c(v_6),c(v_7)\}\subset\{4,\alpha,\beta\}$ for the vertices of the triangle
$v_5v_6v_7$ it follows that $c(v_6)=4$ or
$c(v_7)=4$, which implies $c(v_9)=\beta$ and then $c(v_8)=4$. Hence, the
triangle completely in the interior of $D_1$ must be colored with colors
$\alpha$ and $\beta$, a contradiction.

% Because of the coloring of the triangle $v_5v_6v_7$ it follows that $4\in
% \{c(v_6),c(v_7)\}$ and therefore $c(v_9)=\beta$ and $c(v_8)=4$.
% Hence, the triangle inside $D_1$ must be colored with $\alpha$ and $\beta$, a
% contradiction.

\item Case 2: $c(v_5)=3$

Clearly $\{c(v_8),c(v_9)\}=\{4,\beta\}$, which implies successively that
$c(v_7)=\alpha$, $c(v_4)=\beta$, $c(v_8)=4$, $c(v_9)=\beta$, and finally
$c(v_6)=4$. Consequently, the triangle in the interior of $D_2$ must be
colored with the two colors $\alpha$ and $\beta$, again a contradiction.
\end{itemize}

Secondly, let $v_{10}$ be colored by $\beta$.
This can be handled using analogous arguments by interchanging the roles of
$\alpha$ and $\beta$.


Therefore, the subgraph $G_1$ of $G$ with given precoloring and list
assignment as in Figure~2 is not $L$-list colorable.

\begin{figure}[h] \label{f3} \begin{center}
%\input{k4.tex}
\begin{tikzpicture}[scale=0.6]
\def \1 {(1.0,2.0)}
\def \2 {(9.0,2.0)}
\def \3 {(5.0,4.5)}
\def \4 {(5.0,9.0)}
\def \5 {(5.0,1.0)}
\def \6 {(5.0,3.0)}
\def \7 {(2.0,6.2)}
\def \8 {(4.0,5.1)}
\def \9 {(6.0,5.1)}
\def \a {(8.0,6.2)}
\newcommand \knoten[1] {\draw[fill] #1 circle [radius=0.05];}
\newcommand \dick[1] {\draw[fill] #1 circle [radius=0.1];}

%\draw[fill] \1 circle [radius=0.05];
\dick{\1}
\dick{\2}
\dick{\3}
\dick{\4}
\knoten{\5}
\knoten{\6}
\knoten{\7}
\knoten{\8}
\knoten{\9}
\knoten{\a}
\draw [very thick] \1 --\2 --\3 --\4 --\1 -- \3 --\2 --\4 ;
\draw \1 --\5 --\2 --\6 --\1 --\7 --\4 --\8 --\1 ;
\draw \8 --\3 --\9 --\4 --\8 ;
\draw \4 --\a --\2 --\8 ;
\draw \6 --\3 ;
\draw \2 --\9 ;

\node[above] at \5 {\footnotesize $G_1$};
\node[below] at \6 {\footnotesize $G_1$};
\node[above right] at \6 {\footnotesize $G_1$};
\node[above left] at \6 {\footnotesize $G_1$};
\node[below] at \8 {\footnotesize $G_1$};
\node[above right] at \8 {\footnotesize $G_1$};
\node[above left] at \8 {\footnotesize $G_1$};
\node[below] at \9 {\footnotesize $G_1$};
\node[above right] at \9 {\footnotesize $G_1$};
\node[above left] at \9 {\footnotesize $G_1$};
\node[below right] at \7 {\footnotesize $G_1$};
\node[below left] at \a {\footnotesize $G_1$};
\node[below] at \5 {\footnotesize $u$};
\node[left] at \7 {\footnotesize $v$};
\node[right] at \a {\footnotesize $w$};

\end{tikzpicture}
 \end{center}
\caption{$K_4$ with twelve inserted $G_1$s}
\end{figure}



Next, consider the complete graph $K_4$ where the list of all vertices is
$\{1,2,\alpha,\beta\}$.
Construct the graph $G$ as follows. For every edge $xy$ in $K_4$
add two copies of the graph $G_1$ identifying its edge $v_1v_2$ with the
edge $xy$, once with $x=v_1$ and $y=v_2$ and the other time  with $y=v_1$ and
$x=v_2$ (see Figure~3) and then identify the vertices $u$, $v$, and $w$.



Clearly, two vertices of of $K_4$ must be colored by $1$ and $2$ giving
exactly the above precoloring for one of the corresponding subgraphs $G_1$.
Hence, $G$ is planar and not $L$-list colorable, where all lists of the list
assignment $L$ have length $4$ and contain the elements $\alpha$ and $\beta$.
\end{proof}



Since the vertices $u$, $v$, and $w$ in Figure~3 are identified, the graph $G$ constructed above has $8+12\cdot 13=164$ vertices.


Considering Claim 3 and Theorem 6 we obtain the answer to Problem~2, which also
improves the above mentioned result of Wegner. Moreover, in some sense this
conclusion is a sharpness result for the Four Color Theorem.

\begin{corollary}
There is a planar graph $G$ such that in every proper $4$-coloring of $G$ the
vertices of every two color classes induce a subgraph that is non-$2$-list
colorable.
\end{corollary}

Finally, let us mention a related concept introduced by Kratochv\'{i}l et al. in~\cite{KrTuVo98}. A list assignment $L$ for a graph $G=(V,E)$ is called a \emph{ $(k,c)$-assignment} if $L(v)=k$ for all $v\in V(G)$ and $|L(v)\cap L(w)|\leq c$ for all edges $vw\in E(G)$. In~\cite{KrTuVo-2} it is mentioned that every planar graph is $L$-list colorable for every $(4,1)$-assignment $L$. Moreover, there exist planar graphs $G$ and corresponding $(4,3)$-assignments $L$ such that $G$ is not $L$-list colorable. So far, there is no result for $(4,2)$-assignments and the following problem remains open.

\begin{problem}
Is every planar graph $L$-list colorable for every $(4,2)$-assignment $L$?
\end{problem}

\begin{thebibliography}{99}

\newcommand{\au}[1]{{#1\,.\,}}      \newcommand{\ti}[1]{{#1\/.}}
\newcommand{\bkti}[1]{{\emph{ #1}}}         \newcommand{\jou}[1]{{ \emph{#1\/},}}
\newcommand{\vol}[1]{#1:}          \newcommand{\yr}[1]{#1.}
\newcommand{\pp}[1]{#1,}
\def \JCTB {J. Combin. Theory, Ser.~B}
\def \DM {Discrete Math.}
\def \TEJC {Electron. J. Combin.}
\def \AMS {American Math. Society}
\def \JGT {J. Graph Theory}



\bibitem{AppelH89}
\au {K. Appel, W. Haken }
\ti {Every Planar Map is Four Colorable}
\bkti {Contemp. Math. \vol{98}, \AMS, Providence, R.I., \yr{1989}}

\bibitem{Choi}
\au {H. Choi, Y.S. Kwong}
\ti {On $t$-common list colorings}
\jou {\TEJC}
\vol {24(3)}
\pp {\#P3.32}
\yr {2017}

\bibitem{KrTuVo-2}
\au {J. Kratochv\'{i}l, Zs. Tuza, M. Voigt}
\ti {Brooks-Type Theorems for Choosability with Separation}
\jou {\JGT}
\vol {27(1)}
\pp {43--49}
\yr {1998}

\bibitem{KrTuVo98}
\au {J. Kratochv\'{i}l, Zs. Tuza, M. Voigt}
\ti {Complexity of choosing subsets from color sets}
\jou {\DM}
\vol {191}
\pp {139--148}
\yr {1998}

\bibitem{RobSST96a}
\au {N. Robertson, D. P. Sanders, P. Seymor, R. Thomas}
\ti {A new proof of the four-color theorem }
\jou {Electron. Res. Announc. \AMS}
\vol {2}
\pp {17-25}
\yr {1996}

\bibitem {Thom94}
\au {C. Thomassen}
\ti {Every planar graph is 5-choosable}
\jou {\JCTB}
\vol{62}
\pp {180--181}
\yr {1994}

\bibitem {Voig93}
\au {M. Voigt}
\ti {List colorings of planar graphs}
\jou {\DM}
\vol{120}
\pp {215--219}
\yr {1993}

\bibitem {Weg}
\au {G. Wegner}
\ti {Note on a paper of B. Gr\"unbaum on acyclic colorings}
\jou {Israel J. Math.}
\vol{14}
\pp {409--412}
\yr {1973}

\end{thebibliography}
\end{document}