Facial colourings of plane graphs

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}

Back to all abstracts