Colouring Planar Mixed Hypergraphs
Colouring Planar Mixed Hypergraphs
复制标题
DOI：
10.37236/1538
复制
发表时间：
2000-09
期刊：
影响因子：
--
通讯作者：
André Kündgen;E. Mendelsohn;V. Voloshin
中科院分区：
文献类型：
--
作者：
André Kündgen;E. Mendelsohn;V. Voloshin
混合超图是一个三元组${\cal H} = (V,{\cal C}, {\cal D})\；其中$V$是顶点集，${\cal}$和${\cal D}$分别是$V$的子集族，${\cal C}$-边和${\cal D}$-边。${\cal H}$的$k$着色是一个映射$c: V\右行[k]$，使得每个${\cal c}$边至少有两个具有${\cal c}$共同颜色的顶点，并且每个${\cal D}$边至少有两个具有${\cal D}$不同颜色的顶点。${\cal H}$称为平面混合超图，如果它的二部表示是一个平面图。经典图是混合超图的特殊情况，当${\cal C}=\emptyset$和所有${\cal D}$-边的大小为2时，而在双超图中${\cal C}= {\cal D}$。研究了平面混合超图的着色性质。具体地说，我们证明了极大平面双超图是2色的，找到了它们的色多项式和对偶中2因子的色谱的公式，证明了它们的色谱是无间隙的，并提供了对一个着色中最大色数的一个尖锐估计。
A mixed hypergraph is a triple ${\cal H} = (V,{\cal C}, {\cal D})\;$ where $V$ is the vertex set and ${\cal C}$ and ${\cal D}$ are families of subsets of $V$, the ${\cal C}$-edges and ${\cal D}$-edges, respectively. A $k$-colouring of ${\cal H}$ is a mapping $c: V\rightarrow [k]$ such that each ${\cal C}$-edge has at least two vertices with a ${\cal C}$ommon colour and each ${\cal D}$-edge has at least two vertices of ${\cal D}$ifferent colours. ${\cal H}$ is called a planar mixed hypergraph if its bipartite representation is a planar graph. Classic graphs are the special case of mixed hypergraphs when ${\cal C}=\emptyset$ and all the ${\cal D}$-edges have size 2, whereas in a bi-hypergraph ${\cal C} = {\cal D}$. 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.