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}

Back to all abstracts