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}