# Facial colourings of plane graphs

###
Stanislav Jendroľ

P. J. Šafárik University in Košice

####
Igor Fabrici

P. J. Šafárik University in Košice

####
Michaela Vrbjarová

P. J. Šafárik University in Košice

PDF

**Minisymposium:**
VERTEX COLOURINGS AND FORBIDDEN SUBGRAPHS

**Content:**
Let $G=(V,E,F)$ be a connected loopless and bridgeless plane graph, with vertex set $V$, edge set $E$, and face set $F$. Let $X\in\{V,E,F,V\cup E,V\cup F,E\cup F,V\cup E\cup F\}$: Two elements $x$ and $y$ of $X$ are \emph{facially adjacent} in $G$ if they are incident, or they are adjacent vertices, or adjacent faces, or facially adjacent edges (i.e.~edges that are consecutive on the boundary walk of a face of $G$).
A $k$-colouring is facial with respect to $X$ if there is a $k$-colouring of elements of $X$ such that facially adjacent elements of $X$ receive different colours. It is known that:
\begin{enumerate}
\item $G$ has a facial 4-colouring with respect to $X\in\{V,F\}$. The bound 4 is tight. (The~Four Colour Theorem, Appel and Haken 1976)
\item $G$ has a facial 6-colouring with respect to $X=V\cup F$. The bound 6 is tight. (The Six Colour Theorem, Borodin 1984)\par
We prove that:
\item $G$ has a facial 4-colouring with respect to $X=E$. The bound 4 is tight.
\item $G$ has a facial 6-colouring with respect to $X\in\{V\cup E, E\cup F\}$. There are graphs required 5 colours in such a colouring.
\item $G$ has a facial 8-colouring with respect to $X=V\cup E\cup F$. There is a graph requiring 7 colours in such a colouring.
\end{enumerate}