%Latex2e file for 16pages (37k)
% last update by VV, Sept.29, 2000 <-- reference updated
% last changed by AK, Sept 28, 2000 <-- incorporated ref report.
\documentclass[12pt]{article}
\usepackage{amsmath,amssymb,xy}
\pagestyle{myheadings}
\markright{\sc the electronic journal of combinatorics \textbf{7}
(2000), \#R60\hfill}
\thispagestyle{empty}
\setlength{\textwidth}{6.3in}
\setlength{\oddsidemargin}{0in}
\setlength{\evensidemargin}{0in}
\setlength{\topmargin}{0in}
\setlength{\textheight}{8.5in}
\def \version {Submitted: June 5, 2000;
Accepted September 28, 2000}
\begin{document}
\newtheorem{theorem}{Theorem}%[section]%
\newtheorem{defin}{Definition}%[section]%
\newtheorem{lemma}[theorem]{Lemma}%
\newtheorem{problem}{Problem}
\newtheorem{cor}{Corollary}
\newtheorem{pr}{Proposition}
\newtheorem{example}{Example}
\def \beg {\begin{example}}
\def \eeg {\end{example}}
\def \bpr {\begin{pr}}
\def \epr {\end{pr}}
\def \bt {\begin{theorem}}
\def \et {\end{theorem}}
\def \bcor {\begin{cor}}
\def \ecor {\end{cor}}
\def \bdf {\begin{defin}}
\def \edf {\end{defin}}
\def \bl {\begin{lemma}}
\def \el {\end{lemma}}
\def \be {\begin{enumerate}}
\def \ee {\end{enumerate}}
\def \bd {\begin{description}}
\def \ed {\end{description}}
\def \beq {\begin{equation}}
\def \eeq {\end{equation}}
\def \qed {\hfill \mbox{\rule{2.5mm}{2.75mm}}\medskip}
\def \uc {\bar \chi}
\def \uch {\bar \chi ({\cal H})}
\def \cA {{\cal A}}
\def \cB {{\cal B}}
\def \cC {{\cal C}}
\def \cD {{\cal D}}
\def \cE {{\cal E}}
\def \cF {{\cal F}}
\def \cG {{\cal G}}
\def \cH {{\cal H}}
\def \cI {{\cal I}}
\def \cJ {{\cal J}}
\def \cK {{\cal K}}
\def \cL {{\cal L}}
\def \cM {{\cal M}}
\def \cN {{\cal N}}
\def \cO {{\cal O}}
\def \cP {{\cal P}}
\def \cQ {{\cal Q}}
\def \cR {{\cal R}}
\def \cS {{\cal S}}
\def \cT {{\cal T}}
\def \cU {{\cal U}}
\def \cV {{\cal V}}
\def \cW {{\cal W}}
\def \cX {{\cal X}}
\def \cY {{\cal Y}}
\def \cZ {{\cal Z}}
\def\Z{\mathbb Z}
\def \HH {$\cH=(V,\cC, \cD)\;$}
\def \HHp {$\cH'=(V',\cC', \cD)$}
\def \mh {mixed hypergraph}
\def \ucmh {uc-hyper\-graph}
\def \bit {bi-triangu\-lation}
\def \bits {bi-triangulations}
\def \ssk {\smallskip}
\def \msk {\medskip}
\def \bsk {\bigskip}
\def \nin {\noindent}
\def \pf {\nin{\bf Proof.}\quad}
\def \spf {\nin{\bf Sketch of Proof.}\quad}
\def \nsz {\normalsize}
\date{\version}
\title{Colouring planar mixed hypergraphs}
\author{Andr\'e K\"undgen\thanks{Supported by NSERC grant
of Derek Corneil and the Fields Institute.}\\
{\nsz The Fields Institute}\\
{\nsz 222 College St. }\\
{\nsz Toronto, Ont.\quad M5T 3J1 }\\
{\nsz Canada}\\
{\nsz {\small kundgen@member.ams.org}}
\and
Eric Mendelsohn\thanks{This research is supported by NSERC Canada
OGP007621 and the Fields Institute.}\\
{\nsz Department of Mathematics}\\
{\nsz University of Toronto}\\
{\nsz 100 St. George St., Toronto, Ont., }\\
{\nsz Canada}\\
{\nsz {\small mendelso@math.utoronto.ca}}
\and
Vitaly Voloshin\thanks{This research is supported by NSERC Canada
OGP007621, OGP007268 and the Fields Institute. } \\
{\nsz Institute of Mathematics and Informatics}\\
{\nsz Moldavian Academy of Sciences}\\
{\nsz Academiei, 5, Chi\c{s}in\u{a}u, MD-2028} \\
{\nsz Moldova}\\
{\nsz {\small voloshin@math.mldnet.com}}}
\maketitle
\begin{abstract}
A mixed hypergraph is a triple \HH
where $V$ is the vertex set and $\cC$ and $\cD$ are families
of subsets of $V$, the $\cC$-edges and $\cD$-edges,
respectively. A $k$-colouring of $\cH$ is a mapping
$c: V\rightarrow [k]$ such that each $\cC$-edge has
at least two vertices with a $\cC$ommon colour and each $\cD$-edge
has at least two vertices of $\cD$ifferent colours.
$\cH$ is called a planar mixed hypergraph if its bipartite
representation is a planar graph.
Classic graphs are the special case of mixed
hypergraphs when $\cC=\emptyset$ and all the $\cD$-edges have
size 2, whereas in a bi-hypergraph $\cC=\cD$.
We investigate the colouring properties of planar mixed hypergraphs.
Specifically, we show that maximal planar bi-hypergraphs are
2-colourable, find formulas for their chromatic polynomial and
chromatic spectrum in terms of 2-factors in the dual,
prove that their chromatic spectrum is gap-free and provide
a sharp estimate on the maximum number of colours in a colouring.
\bigskip
{\bf Keywords:} colourings of hypergraphs, mixed hypergraphs,
planar graphs and hypergraphs, colourability, chromatic spectrum.
\bigskip
{\bf 2000 Mathematics Subject Classification:} 05C15.\quad
\end{abstract}
\section{Introduction}
We use the standard graph and hypergraph terminology of
Berge~\cite{Ber1,Ber2} and the mixed hypergraph terminology
from \cite{TuzVol,TuzVolZho,Vol1,Vol2}.
Following Berge~\cite{Ber1,Ber2} a {\it hypergraph} is a pair $(V,\cE)$
where $V$ is the set of {\it vertices} and $\cE$ is a family of
subsets of $V$ (of size at least 2), the {\it edges}.
We use this notation mainly when we discuss general
properties. When we consider colouring properties specifically,
we shall use the language of mixed hypergraphs.
A {\it mixed hypergraph} is a triple \HH where $V$ is the
vertex set, $|V|=n$, and $\cC$ and $\cD$ are families of subsets
of $V$, the $\cC$-{\it edges} and $\cD$-{\it edges}.
A {\it (proper) $k$-colouring} of a mixed hypergraph is a mapping
$c: V \rightarrow \{1,2,\ldots,k\}$ from the vertex set $V$ into
a set of $k$ colours so that each $\cC$-edge has at least two
vertices with $\cC$ommon colour and each
$\cD$-edge has at least two vertices with $\cD$ifferent colours.
A {\it strict} $k$-colouring is a proper colouring using all $k$
colours. If a mixed hypergraph $\cH$ has at least one
colouring, then $\cH$ is called {\it colourable}. Otherwise $\cH$ is
called {\it uncolourable}.
Let $P(\cH,k)$ denote the number of proper $k$-colorings of $\cH$.
It can be seen that $P(\cH,k)$ is a polynomial in $k$, known as
the {\it chromatic polynomial} of $\cH$.
By $c(v)$ we denote the colour of vertex $v\in V$ in the colouring $c$.
A set of vertices is {\it monochromatic} in a colouring if
all the vertices of the set have the same colour. Similarly
a set is {\it polychromatic} if no two vertices in it
have the same colour. Thus in a proper colouring $\cC$-edges
must be non-polychromatic subsets, and $\cD$-edges non-monochromatic
subsets of vertices.
If $\cH$ is colourable then the minimum number of colours over all
colourings is the {\it lower chromatic number} $\chi(\cH)$.
The maximum number of colours in all strict colourings of $\cH$ is
its {\it upper chromatic number} $\bar\chi(\cH)$.
For each $k$, $1\le k \le n$, let $r_k$ be the number of partitions
of the vertex set into $k$ nonempty parts (colour classes) such that
the colouring constraint is satisfied on each $\cC$- and $\cD$-edge.
We call these partitions {\it feasible}.
Thus $r_k$ is the number of different strict $k$-colourings of
$\cH$ if we disregard permutations of colours.
The vector $$R(\cH)=(r_1,\ldots,r_n)=(0, \ldots, 0, r_{\chi(\cH)},
\ldots , r_{\uch}, 0, \ldots , 0)$$
\nin is the {\it chromatic spectrum} of $\cH$.
The set of values $k$ such that $\cH$ has a strict $k$-colouring
is the {\it feasible set} of $\cH$; this is
the set of indices $i$ such that $r_i >0$.
A mixed hypergraph has a {\it gap at $k$} if its
feasible set contains elements larger and smaller than $k$ but
omits $k$. A mixed hypergraph $\cH$ is called
{\it uniquely colourable}~\cite{TuzVolZho}
if it has precisely one feasible partition.
A mixed hypergraph \HH is called {\it reduced} if every $\cC$-edge
is of size at least 3, every $\cD$-edge is of size at least 2,
and moreover no $\cC$-edge ($\cD$-edge) is included in another
$\cC$-edge ($\cD$-edge). It follows from the splitting-contraction
algorithm \cite{Vol1,Vol2} that the colouring properties of an
arbitrary mixed hypergraph may be obtained from its reduced
mixed hypergraph. Therefore, unless otherwise stated, we consider
only reduced mixed hypergraphs.
If $\cH=(V,\cC,\cD)$
is a mixed hypergraph, then the subhypergraph {\it induced} by
$V'\subseteq V$ is the mixed hypergraph $\cH'=(V',\cC',\cD')$
defined by setting $\cC'=\{C\in \cC:~C\subseteq V'\}$,
$\cD'=\{D\in \cD:~D\subseteq V'\}$ and denoted by $\cH'=\cH/V'$.
%A mixed hypergraph $\cH'=(V',\cC',\cD')$ is a {\it partial mixed
%hypergraph} if $V'\subseteq V, \cC'\subseteq \cC, \cD'\subseteq \cD.$
A mixed hypergraph $\cH=(V,\emptyset,\cD)$
($\cH=(V,\cC,\emptyset)$) is called a "$\cD$-hypergraph"
("$\cC$-hypergraph") and denoted by $\cH_{\cD}$ ($\cH_{\cC}$).
If $\cH_{\cD}$ contains only $\cD$-edges of size 2 then it coincides
with the usual notion of a graph.
A mixed hypergraph \HH is called a {\it bi-hypergraph}
iff $\cC=\cD$. A subset of vertices which is both
a $\cC$-edge and $\cD$-edge is called a {\it bi-edge}.
The study of mixed hypergraphs has made a lot of progress
since its inception~\cite{Vol2}. It has
many potential applications, since mixed hypergraphs can be used to
encode various partitioning constraints. They have been used to model
problems in such areas as colouring of block designs~\cite{CDR,ColRos},
list-colouring of graphs~\cite{TuzVol}, integer
programming~\cite{TuzVol} and other areas. In this paper we begin a
systematic study of planar mixed hypergraphs.
\section{Planar hypergraphs}
Let $\cH=(V,\cE)$ be a hypergraph.
\bdf
The {\it bipartite representation} of $\cH$, denoted by $B(\cH)$,
is a bipartite graph with vertex set $V\cup\cE$.
$v\in V$ is adjacent to $E \in\cE$ (in $B(\cH)$) if and only if
$v\in E$.
\edf
The following definition is due to Zykov~\cite{Zyk}:
\bdf
A hypergraph $\cH$ is called {\it planar}
iff $B(\cH)$ is a planar graph.
\edf
Thus planar graphs are the special case of planar hypergraphs
in which all edges have size~2.
As one may see, a planar hypergraph admits an embedding on
the plane in such a way that each vertex corresponds to a point
on the plane, and every edge corresponds to a
closed region homeomorphic to a disk such that it contains
the points corresponding to its vertices in the boundary
and it does not contain the points corresponding to the other
vertices. Furthermore two such regions intersect exactly in
the points that correspond to the vertices in the intersection
of the corresponding edges. In this way the connected regions
of the plane which do not correspond to the edges form the
faces of the embedding of the planar hypergraph.
Using properties of the bipartite representation $B(\cH)$ one
can derive many properties of a planar embedding of the
hypergraph $\cH$~\cite{Ber1,Ber2,Zyk}. For example
if the degree of vertex $v\in V$ in $\cH$ is denoted by
$d_\cH(v)$ we obtain
\bt [Euler's formula]
If $\cH=(V,\cE)$ is a planar hypergraph embedded on the
plane with $f$ faces, then
$$ |V|+|\cE| - \sum_{E\in\cE}|E|+f
=|V|+|\cE|-\sum_{v\in V}d_\cH(v)+f=2.$$
\et
\pf This follows from Euler's formula for $B(\cH)$.
\qed
\bdf
An embedding of a planar hypergraph is called maximal iff
every face contains precisely two vertices, or equivalently
iff in the corresponding embedding of $B(\cH)$ every face has
length 4.
\edf
This maximality is relative in the sense that in every such face
one can always insert a new edge of size 2.
However if a planar hypergraph $\cH$ is not maximal then there
is at least one face of size at least 3 and therefore one can
insert a new edge of size at least 3 in that face.
If we draw the faces of a maximal planar hypergraph as curves
connecting respective vertices then we obtain a plane graph
whose faces correspond to the edges of the initial hypergraph.
In this way, we may look at a plane graph as a planar embedding
of a maximal hypergraph such that the faces of the graph
correspond to the edges of the hypergraph.
\section{Colouring planar mixed hypergraphs}
Let \HH be a mixed hypergraph. Denote the underlying edge-set
of $\cH$ by $\cE=\cC\cup\cD$. Observe that if some $\cC$-edge
coincides as a subset of vertices with some $\cD$-edge
(i.e. it is a bi-edge) then it appears only once in $\cE$.
We say that $\cH '=(V,\cE)$ is the {\it underlying hypergraph}
of $\cH$.
\bdf
We call a mixed hypergraph \HH planar if and only if the underlying
hypergraph $\cH '$ is planar.
\edf
This can be viewed as follows: we can embed $\cH '$ in the plane
and label all hyperedges with $b$, $c$ or $d$ appropriately
according to whether they are bi-edges, $\cC$-edges or $\cD$-edges.
Note that $\cC$-edges of size 2 can be contracted,
and bi-edges of size
2 lead to uncolourability, so that in general it suffices
to only consider mixed hypergraphs containing neither.
\beg Clearly not every mixed hypergraph is planar.
Let $\cH_7$ be the \\
3-uniform hypergraph with vertex-set $V(\cH_7)=\Z_7$, and edge-set
$\cE(\cH_7)=\left\{ \{0+i,1+i, 3+i\},\{0+i,2+i, 3+i\}\ |\ i\in
\Z_7 \right\}$. In $\cH_7$ every pair of vertices appears in
exactly 2 edges, but $B(\cH_7)$ has 21 vertices,
42 edges and girth 4, and is therefore not planar.
It can also be proved by exhaustion in a few
tedious minutes that $\cH_7$ is uncolourable as a bi-hypergraph.
It is worth noting that $\cH_7$ is embeddable in the torus:
The faces of the standard embedding of $K_7$ on the torus,
shown in Figure~1, are precisely $\cE(\cH_7)$.
We note also that the edges of this hypergraph are the blocks of
the unique simple $S(7,3,2)$ design. The study of designs as
mixed hypergraphs is also an important emerging subfield~\cite{CDR}.
\eeg
\bigskip
\vbox{\centerline{\xy /r5pc/:,
{(0,0);(3,0)**@{.}},
{(0,0);(0,-2)**@{.}},
{(0,-2);(3,-2)**@{.}},
{(3,-2);(3,0)**@{.}},
%% outside box
{(0,-2);(1,0)**@{-}},
{(1,-2);(2,0)**@{-}},
{(2,-2);(3,0)**@{-}},
%% three diagonal lines
{(0,0);(3,-1)**@{-}},
{(3,-2);(0,-1)**@{-}},
%% two from left to right
(3,-1.333);(1.5,-2)**@{-},
(0,-2);(3,-0.666)**@{-},
(3,0);(0,-1.333)**@{-},
(0,-0.666);(1.5,0)**@{-},
(0,0)*{\bullet},
(3,0)*{\bullet},
(0,-2)*{\bullet},
(3,-2)*{\bullet},
(0.86,-0.29)*{\bullet},
(2.145,-1.715)*{\bullet},
(1.285,-1.43)*{\bullet},
(0.43,-1.145)*{\bullet},
(2.57,-0.855)*{\bullet},
(1.715,-0.575)*{\bullet},
(-0.15,0)*{0},(-0.15,-2)*{0},(3.15,0)*{0},(3.15,-2)*{0},
(0.9,-0.4)*{1},(1.75,-0.7)*{2},(2.6,-0.97)*{3},
(0.46,-1.24)*{4},(1.315,-1.55)*{5},(2.2,-1.84)*{6},
\endxy}\medskip
\centerline{Figure~1: An embedding of $K_7$ on the torus}}
\medskip
A first discussion on the colouring of planar hypergraphs
can be found in a paper of Zykov~\cite{Zyk}.
%AK
The main results discussed there may be reformulated in
the language of mixed hypergraphs as follows.
\bt[Bulitco]
The Four colour theorems for planar graphs and for planar
$\cD$-hypergraphs are equivalent.
\et
\bt[Burshtein, Kostochka]
If a planar $\cD$-hypergraph contains at most one $\cD$-edge of
size 2 then $\chi (\cH)\le 2.$
\et
The question of colouring properties of general
planar mixed hypergraphs was first raised in~\cite{Vol2}
(problem 8, p.43). It is evident that every planar $\cD$-hypergraph
is colourable, just as every planar $\cC$-hypergraph is.
The situation changes however if we consider general planar mixed
hypergraphs. The smallest non-trivial (reduced) uncolourable planar
mixed hypergraph \HH is given by $V=\{1,2,3\}, \cC=\{(1,2,3)\},
\cD=\{(1,2),(2,3),(1,3)\}$. It is easy to embed
it on the plane with 4 faces (3 containing 2 vertices each and 1
containing 3 vertices). It is not difficult to extend this example
to an infinite family of uncolourable planar mixed hypergraphs.
Take for example an odd $\cD$-cycle of length $2k+1$
and add to it $k$ triples of the form (1,2,3),(3,4,5),(5,6,7), ...
as $\cC$-edges, see~\cite{VolVos}.
The general structure of uncolourable planar mixed hypergraphs is
unknown, but we will see that the presence of $\cD$-edges of size 2
is crucial. In general $\cD$-edges of size 2 are problematic, since
allowing them implies that the four colour problem is a special case
of the theory of planar mixed hypergraphs.
Since we already excluded $\cC$-edges and bi-edges of size 2, it seems
reasonable to study only planar mixed hypergraphs without edges of
size 2. The first interesting case is that in which \HH is a maximal
3-uniform planar bi-hypergraph. These graphs already have a rich
structure that will allow us to draw interesting conclusions for
the general case, and we will study them in the next section.
\section{Bi-triangulations}
We now consider the colouring problem for maximal 3-uniform planar
bi-hypergraphs $\cH$. Since every face of a maximal planar hypergraph
is of size 2, we can associate a graph $G(\cH)$, on the same vertex
set, with $\cH$: replace every face in $\cH$ by an edge in $G$, so
that every edge in $\cH$ becomes a face of $G$. $\cH$ is maximal
3-uniform, so that $G$ must be a triangulation in the usual sense.
We use $\cH$ and $G$ interchangeably, and since every edge of $\cH$
is a bi-edge, we will refer to them as {\it \bits}.
In this section we will study the colourings of \bits:
we want to colour $V(G)$ so that every face has exactly two
vertices of the same colour.
\bdf
A colouring $c_1$ is a {\it refinement} of a colouring
$c_2$ if every colour class of $c_1$ is contained in a
colour class of $c_2$. A colour class of a colouring $c$
is {\it maximal} if it is a colour class in every refinement
of $c$. If every colour class of $c$ is maximal, then $c$ is
a maximal colouring.
\edf
\bl\label{lemm}
A colour class of a colouring of a \bit~is
maximal if and only if it induces a connected subgraph.
\el
\pf In a triangulation two vertices are together in a face
if and only they are adjacent. Therefore a maximal colour
class must induce a connected subgraph, since otherwise
we can simply recolour one of the components. Conversely,
a connected colour class can not be refined furthermore,
since recolouring some of its vertices would result in
two adjacent vertices from the old colour class receiving
distinct new colours. This leads to a contradiction, since
any face containing these two vertices is now multicoloured.
\qed
Observe that this result does not extend to general
planar graphs, as can be easily seen by colouring $C_4$
with two colours, so that every vertex is adjacent to
a vertex of the same colour. The following results (Theorem~\ref{thm}
and Corollaries~\ref{max} and~\ref{count}) also break down
for $C_4$.
\bt\label{thm}
There is a 1-1 correspondence between the $k$-colourings
of a \bit~$G$ and the $k$-face-colourings of the
2-factors in the dual $G^*$. In this correspondence a
colouring $c_1$ of $G$ is a refinement of a colouring $c_2$
if and only if the corresponding 2-factors are identical and
the face-colouring associated with $c_1$ is a refinement of
the face-colouring associated with $c_2$.
\et
The main idea of the proof is due to Penaud~\cite{Pen} who
essentially showed that there is a 1-1 correspondence between
2-colourings of $G$ and 2-factors of $G^*$. (See Corollary~\ref{count})
\pf
A 2-factor of $G^*$ partitions the plane into regions,
inducing a partition of $V(G)$ into non-empty sets. Thus every
proper face-colouring of this 2-factor with $k$ colours corresponds
to a $k$-colouring of $V(G)$. Such a colouring is in fact a
$k$-colouring of the \bit~$G$, since it follows
from the properness of the face-colouring that in every face
of $G$ there are exactly 2 vertices from one colour class and 1
from another.
Conversely, given a $k$-colouring we can recover the 2-factor
and its face-colouring. Since in every face of $G$ there are
exactly 2 vertices of the same colour we get a 2-regular
spanning subgraph, i.e. a 2-factor, of $G^*$ by taking the
dual edge of every edge in $G$ that is incident to vertices of
different colour. Now, if two vertices are in the same region
(generated by the 2-factor) then there is a curve connecting them
that passes only through vertices in this region. But then consecutive
vertices on this curve must be on the same face and are therefore
adjacent. The edge joining these vertices can not be the dual
of an edge in the 2-factor, since otherwise it would follow
from the Jordan curve theorem that they are in different faces.
By the definition of the 2-factor it follows thus that consecutive
vertices on this curve must be of the same colour, and that therefore
every vertex in a given region has the same colour.
Since every region of the 2-factor must contain at least one vertex
we can therefore uniquely define the colouring of the regions and this
$k$-colouring is a good-colouring since faces are separated by dual
edges and thus adjacent faces contain adjacent vertices of different
colour.
For the second part of the proof observe that a refinement
of the face-colouring of the dual graph clearly leads to a
refinement of the colouring of the \bit. For the converse
suppose that $c_1$ is a refinement of $c_2$. Following the construction
of the dual 2-factor it follows that the 2-factor for $c_1$ must
contain the 2-factor for $c_2$, from which it follows that they are
identical. It follows that the face-colouring corresponding
to $c_1$ must be a refinement of the colouring for $c_2$.
\qed
\bdf
Recall that $r_k(G)$ is the number of different strict
$k$-colourings of $G$
(disregarding permutations of colors),
i.e. the number of partitions of $V(G)$
into $k$ non-empty sets that describe a good-colouring of the mixed
hypergraph $G$. Let $S(n,k)$ denote the {\it Stirling numbers of
the second kind}, i.e. the number of ways of partitioning a set
of $n$ elements into exactly $k$ sets. Also define $f_k(G^*)$
to be the number of 2-factors of $G^*$ that consist of exactly
$k$ components, and let $f(G^*)=\sum_{i\geq 1}f_i(G^*)$ be the total
number of 2-factors of~$G^*$.
\edf
\bcor\label{max}
Every colouring of a \bit~$G$ can be refined to
a unique maximal colouring. Furthermore, there are exactly
$f_{k-1}(G^*)$ maximal $k$-colourings of $G$.
\ecor
\pf
By the Jordan curve theorem a given 2-factor consisting
of $k-1$ cycles divides the plane into $k$ regions and by
Lemma~\ref{lemm} the colouring that assigns a different colour to each
face must be the unique maximal colouring for this 2-factor,
since (as it was shown in the proof above) the vertices in
every region induce a connected subgraph. The second statement
follows immediately. All refinements of a given colouring
correspond to the same 2-factor, so that the first statement
also follows.\qed
\bcor\label{count}
A \bit~$G$ has exactly $2f(G^*)$
proper 2-colourings. In general,
$$r_k(G)=\sum_{i\geq 1}S(i,k-1)f_i(G^*), \rm{~and}$$
$$P(\cH,\lambda)=\sum_{i\geq 1}f_i(G^*)\lambda (\lambda-1)^i.$$
\ecor
\pf
The first statement follows from both summation formulas, by setting
$k=2$ or $\lambda =2$ respectively. For the first formula it suffices
by Theorem~\ref{thm} to show that every 2-factor consisting
of $i$ cycles can be $k$-face-coloured in exactly $S(i,k-1)$ ways.
To see this, create a graph whose vertex-set are the faces in the dual
of the 2-factor, and two vertices are adjacent if and only if
the corresponding faces are separated by a 2-factor. This graph
is connected and has $i$ edges. By the Jordan curve theorem it
has exactly $i+1$ vertices and must therefore form a tree $T$.
Let $r_k(T)$ be the number of proper $k$-colourings of $T$. To
see that $r_k(T)=S(e(T),k-1)$, observe that $r_1(K_1)=1$ and
$r_k(K_1)=0$ for $k\geq 2$. By removing a leaf $v$ we can see that
$r_k(T)=(k-1)r_k(T-v)+r_{k-1}(T-v)$, the usual recursion for
the Stirling numbers. For the second formula it now suffices to
observe that the chromatic polynomial for a tree on $i+1$ vertices
is $\lambda (\lambda -1)^i$.\qed
Jiang, Mubayi, Tuza, Voloshin and West~\cite{JMTVW}
have exhibited mixed hypergraphs whose chromatic spectrum is
not an interval, i.e. there may be some zeroes between
positive components. This can not happen for \bits.
\bcor\label{unbroken}
The spectrum of every \bit~$G$ is unbroken, $\chi(G)=2$ and
$\uc(G)=1+\max\{k:f_k(G^*)\geq 1\}$.
\ecor
\pf
Since $G^*$ is a 3-regular bridgeless
graph it follows from Petersen's theorem that it has a 2-factor.
So by Corollary~\ref{count} every \bit~is 2-colourable,
and therefore must have lower chromatic number 2. A colouring
achieving the upper chromatic number must be maximal,
so that the value of $\uc(G)$ follows from Corollary~\ref{max}.
If $k=\uc(G)$, then $f_{k-1}(G^*)\geq 1$, so since
$S(k-1,i-1)\geq 1$ for every $2\leq i\leq k$, we get that
$r_i(G)\geq 1$ in this range and the spectrum is unbroken.
Furthermore an $i$-colouring can be obtained from an $i$-colouring
of the tree.\qed
\bcor\label{bicol}
Every planar mixed hypergraph without edges of size 2
can be 2-coloured.
\ecor
\pf
Without loss of generality
we may assume that the mixed hypergraph is a maximal
bi-hypergraph, since adding $\cC$- or $\cD$-edges only decreases
the number of 2-colourings. Similarly, if $G$ contains any faces
of size larger than 3, then those can be divided into faces of
size 3 by adding graph edges to obtain a \bit. The result
now follows from Corollary~\ref{unbroken}.\qed
\bcor\label{notunique}
Every uniquely colourable planar mixed hypergraph
must have an edge of size~2.
\ecor
\pf Suppose that $G$ is uniquely colourable, and free of edges of
size 2. Again we may assume that $G$ is a \bit.
By Corollary~\ref{unbroken}, $\uc(G)=2$, so that by
Corollary~\ref{count}, $G^*$ must have a unique 2-factor:
a Hamiltonian cycle. This contradicts the following theorem.
\qed %
\bt [Thomason~\cite{Thomason}, Tutte~\cite{Tutte}
``Smith's Theorem''] \label {TT}
The \\ number of Hamiltonian cycles through a given edge of a cubic
graph is even.
\et
\pf We sketch the elegant proof of Thomason.
Let $uv$ be the given edge.
Consider the graph whose {\bf vertices} are the Hamiltonian
paths starting at $u$ with edge $uv$. Two such paths are adjacent
if one can be obtained from the other by adding an edge at the
end of the path and deleting a different edge. Now vertices of
degree 1 in this graph correspond to Hamiltonian cycles containing
$uv$ and all other vertices have degree 2.
Thus the number of Hamiltonian cycles containing $uv$ is even.
\qed
\beg
Consider the \bit~corresponding to $K_4$, i.e. \HH with
$V=\{1,2,3,4\}, \cC=\cD=\{(123),(234),(341),(412)\}$. It
is easy to see that $K_4$ is self-dual and that all 2-factors
of $K_4$ are Hamiltonian. Thus $\chi (\cH)=\bar\chi (\cH)=2$.
One can also verify that the strict colourings
with two colours are 1212, 1122, 2112 and the corresponding three
2-factors of $G^*$ are 12341, 13241 and 12431, so that the chromatic
spectrum is $R(\cH)=(0,3,0,0)$ and the chromatic polynomial is
$3\lambda(\lambda-1)$.
\eeg
\section{Bounds for the upper chromatic number}
Recall that the upper chromatic number of a $\cD$-hypergraph
on $n$ vertices is always $n$. If we have at least one
$\cC$-edge then we have $\uc\leq n-1$. Perhaps surprisingly,
this bound can be achieved even for the restricted class of
\bits.
\bdf
If we replace an edge $ab$ of a graph by creating a new digon $cd$
and including the edges $ac$ and $bd$, then we say that we are {\it
inserting a digon}. The new graph is cubic if and only if the
original graph was cubic.
Similarly, {\it inserting a $K_4-e$} corresponds to removing the edge
$ab$, creating 4 new vertices $\{c,d,e,f\}$ and including the
edges $\{ac,bd,ce,cf,de,df,ef\}$.
$C_3^*$ is the 2-vertex graph consisting of a triple-edge.
\edf
\beg
Let $C_{2n}'$ denote the cubic graph on $2n$ vertices that is
obtained by replacing every edge of a perfect matching in $C_{2n}$
by a double-edge. $C_{2n}'$ can also be built recursively by
inserting $n-1$ digons into the same edge of $C_3^*$.
Consider the \bit~on $n$ vertices $\cH$,
with underlying graph $G$, such that $G^*=C_{2n-4}'$. It follows
from Corollary~\ref{unbroken} that $\uc(\cH)=n-1$, since the
$n-2$ digons form a 2-factor in $G^*$ with the maximum
number of cycles.
\eeg
It can be seen that this is the unique $n$-vertex \bit
~that achieves the bound. We notice that in the example $\cH$,
$G$ and $G^*$ all have repeated edges, and this is crucial for
achieving the bound. For this reason we will regard $\cE$ as
a multi-set, i.e. we keep track of how many copies there are
of each bi-edge.
\bl\label{multi}
Let $\cH$ be the \bit~corresponding to a triangulation $G$
other than $C_3$.
\begin{enumerate}
\item\label{L1} An edge of $\cH$ can be repeated at most twice.
\item\label{L2} If $G^*$ has repeated edges, then $G$ has
repeated edges.
\item\label{L3} Every pair of vertices in $G^*$ that form a digon
gives rise to a unique pair of repeated edges in $\cH$.
\item\label{L4} $G^*$ has repeated edges if and only if
$\cH$ has repeated edges.
\end{enumerate}
\el
\pf For~\ref{L1}.~consider the edge $abc$ in $\cH$ and suppose that
in $G$ the edge $ab$ appears $k$ times. The $k$ copies of $ab$ divide
the plane into $k$ regions, only one of which can contain $c$.
Thus $abc$ is repeated at most twice.
For the remaining parts suppose that $ab$ is a repeated edge of $G^*$
and let $ax$ and $by$ be the remaining edges at $a$ and $b$
respectively. If $x=b$, then $y=a$ and $G^*$ is a triple-edge,
so that $G=C_3$. Otherwise $ab$ forms a digon. Because
$G^*$ is 2-connected (as the dual of a planar graph) both $x$ and $y$
must be internal or external to the digon, so that the digon forms a
face $C$ in $G^*$. Furthermore, every face in $G^*$ containing $ax$
must also contain a copy of $ab$ and $by$. There are exactly two such
faces $A$ and $B$. So the edges in $G$ that are dual to $ax$ and $by$
must be two copies of the edge $AB$, proving~\ref{L2}.
For~\ref{L3}.~observe that $\{ABC\}$ is a repeated edge of $\cH$,
once corresponding to $a$ and once to $b$.
For~\ref{L4}.~it now suffices to prove the reverse implication, so
suppose that $ABC$ appears twice. If $AB$ and $AC$ are not
repeated, then the two faces $ABC$ are connected by exactly two edges
$BC$ and $AC$, forming a digon in $G^*$.
\qed
The reverse implications in Lemma~\ref{multi}.\ref{L2}/\ref{L3}
need not hold in general.
\beg\label{norep}
Let $C_{2n}''$ be the cubic graph on $4n$ vertices obtained by
inserting $n-1$ copies of $K_4-e$ into the same edge of $K_4$.
If we again let $G^*=C_{2n}''$, then $G^*$ and $\cH$ have no
repeated edges, but $G$ forms a \bit~with multiple edges.
\eeg
\beg
Let $\Theta'$ be the cubic graph on $8$ vertices obtained by inserting
a digon into every edge of $C_3^*$. So $\Theta'$ has 3 digons, but
the corresponding hypergraph contains 4 pairs of identical hyperedges.
\eeg
\bt
If $\cH$ is a \bit~with $n$ vertices and $m$ repeated edges, then
$\uc(\cH)\leq \lfloor (2n+m-1)/3\rfloor$ and this bound is sharp.
\et
\pf Let $\cH$ have $G$ as its underlying graph, and suppose
that $G^*$ contains $d$ digons. We first notice that the digons
are vertex-disjoint (since $G^*$ is cubic) and by
Lemma~\ref{multi}.\ref{L3} we get $d\leq m$.
In a 2-factor of $G^*$ with the maximum number of cycles every vertex
not in a digon must be in a cycle of length at least 3. Thus, since
$G^*$ has exactly $n^*=2n-4$ vertices, such a 2-factor has at most
$d+(n^*-2d)/3$ cycles and therefore:
$$\uc(\cH)\leq 1+d+\left\lfloor\frac{2n-4-2d}3\right\rfloor=
\left\lfloor\frac{2n+d-1}3\right\rfloor
\leq\left\lfloor\frac{2n+m-1}3\right\rfloor.$$
We shall now prove that the upper bound is sharp by constructing
the appropriate cubic planar graph $G^*$. In a
$Y$-$\Delta$ transformation of a cubic graph a vertex $v$
with neighbors $w_1,w_2,w_3$ is
replaced by a triangle $v_1v_2v_3$ as follows:
Remove $v$, and introduce new vertices $v_1, v_2, v_3$ and the edges
$\{v_1v_2, v_1v_3, v_2v_3, v_1w_1, v_2w_2, v_3w_3\}$. The new graph
is still cubic planar and there are no multiple edges involving the
new vertices.
Let $2n-4-2m=3t+r$ with $0\leq r\leq 2$. Observe that $t-r$ must
be even and suppose that $t>r$, so that $C_{t-r}'$ is a cubic planar
graph. Perform a $Y$-$\Delta$ transformation at every vertex in
$C_{t-r}'$ to obtain a simple cubic planar graph on $3t-3r$ vertices
that contains exactly $t-r$ disjoint triangles. Next pick an edge
$uv$ that is not contained in a triangle and insert $r$
$K_4-e$'s into $uv$. We now have a graph $G_0$ on $3t+r$ vertices
which contains a 2-factor consisting of $t$ cycles. If $0