Selective hypergraph colourings

详细信息    查看全文

• 作者：Yair Caro^a ; ^{yacaro@kvgeva.org.il" class="auth_mail" title="E-mail the corresponding author} ; Josef Lauri^b ; ^{josef.lauri@um.edu.mt" class="auth_mail" title="E-mail the corresponding author} ; Christina Zarb^b ; ^{christina.zarb@um.edu.mt" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Hypergraphs ; Vertex colourings ; Chromatic spectrum
• 刊名：Discrete Mathematics
• 出版年：2016
• 出版时间：6 April 2016
• 年：2016
• 卷：339
• 期：4
• 页码：1232-1241
• 全文大小：412 K

文摘

We look at colourings of r$r$-uniform hypergraphs, focusing our attention on unique colourability and gaps in the chromatic spectrum. The pattern of an edge E$E$ in an r$r$-uniform hypergraph H$H$ whose vertices are coloured is the partition of r$r$ induced by the colour classes of the vertices in E$E$. Let Q$Q$ be a set of partitions of r$r$. A Q$Q$-colouring of H$H$ is a colouring of its vertices such that only patterns appearing in Q$Q$ are allowed. We first show that many known hypergraph colouring problems, including Ramsey theory, can be stated in the language of Q$Q$-colourings. Then, using as our main tools the notions of Q$Q$-colourings and Σ$\Sigma$-hypergraphs, we define and prove a result on tight colourings, which is a strengthening of the notion of unique colourability. Σ$\Sigma$-hypergraphs are a natural generalisation of σ$\sigma$-hypergraphs introduced by the first two authors in an earlier paper. We also show that there exist Σ$\Sigma$-hypergraphs with arbitrarily large Q$Q$-chromatic number and chromatic number but with bounded clique number. Dvořák et al. have characterised those Q$Q$ which can lead to a hypergraph with a gap in its Q$Q$-spectrum. We give a short direct proof of the necessity of their condition on Q$Q$. We also prove a partial converse for the special case of Σ$\Sigma$-hypergraphs. Finally, we show that, for at least one family Q$Q$ which is known to yield hypergraphs with gaps, there exist no Σ$\Sigma$-hypergraphs with gaps in their Q$Q$-spectrum.