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 class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15004057&_mathId=si3.gif&_user=111111111&_pii=S0012365X15004057&_rdoc=1&_issn=0012365X&md5=29e9aeaa58b6408862f7dda660376369" title="Click to view the MathML source">rclass="mathContainer hidden">class="mathCode">$r$-uniform hypergraphs, focusing our attention on unique colourability and gaps in the chromatic spectrum. The pattern of an edge class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15004057&_mathId=si4.gif&_user=111111111&_pii=S0012365X15004057&_rdoc=1&_issn=0012365X&md5=6ba3f0df561e50f0ff8dd4bcb8e513cb" title="Click to view the MathML source">Eclass="mathContainer hidden">class="mathCode">$E$ in an class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15004057&_mathId=si3.gif&_user=111111111&_pii=S0012365X15004057&_rdoc=1&_issn=0012365X&md5=29e9aeaa58b6408862f7dda660376369" title="Click to view the MathML source">rclass="mathContainer hidden">class="mathCode">$r$-uniform hypergraph class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15004057&_mathId=si6.gif&_user=111111111&_pii=S0012365X15004057&_rdoc=1&_issn=0012365X&md5=5cfc4de18c40c21f0684952b644281b9" title="Click to view the MathML source">Hclass="mathContainer hidden">class="mathCode">$H$ whose vertices are coloured is the partition of class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15004057&_mathId=si3.gif&_user=111111111&_pii=S0012365X15004057&_rdoc=1&_issn=0012365X&md5=29e9aeaa58b6408862f7dda660376369" title="Click to view the MathML source">rclass="mathContainer hidden">class="mathCode">$r$ induced by the colour classes of the vertices in class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15004057&_mathId=si4.gif&_user=111111111&_pii=S0012365X15004057&_rdoc=1&_issn=0012365X&md5=6ba3f0df561e50f0ff8dd4bcb8e513cb" title="Click to view the MathML source">Eclass="mathContainer hidden">class="mathCode">$E$. Let class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15004057&_mathId=si9.gif&_user=111111111&_pii=S0012365X15004057&_rdoc=1&_issn=0012365X&md5=f73088d26ec73f394d9978f89c992c91" title="Click to view the MathML source">Qclass="mathContainer hidden">class="mathCode">$Q$ be a set of partitions of class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15004057&_mathId=si3.gif&_user=111111111&_pii=S0012365X15004057&_rdoc=1&_issn=0012365X&md5=29e9aeaa58b6408862f7dda660376369" title="Click to view the MathML source">rclass="mathContainer hidden">class="mathCode">$r$. A class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15004057&_mathId=si9.gif&_user=111111111&_pii=S0012365X15004057&_rdoc=1&_issn=0012365X&md5=f73088d26ec73f394d9978f89c992c91" title="Click to view the MathML source">Qclass="mathContainer hidden">class="mathCode">$Q$-colouring of class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15004057&_mathId=si6.gif&_user=111111111&_pii=S0012365X15004057&_rdoc=1&_issn=0012365X&md5=5cfc4de18c40c21f0684952b644281b9" title="Click to view the MathML source">Hclass="mathContainer hidden">class="mathCode">$H$ is a colouring of its vertices such that only patterns appearing in class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15004057&_mathId=si9.gif&_user=111111111&_pii=S0012365X15004057&_rdoc=1&_issn=0012365X&md5=f73088d26ec73f394d9978f89c992c91" title="Click to view the MathML source">Qclass="mathContainer hidden">class="mathCode">$Q$ are allowed. We first show that many known hypergraph colouring problems, including Ramsey theory, can be stated in the language of class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15004057&_mathId=si9.gif&_user=111111111&_pii=S0012365X15004057&_rdoc=1&_issn=0012365X&md5=f73088d26ec73f394d9978f89c992c91" title="Click to view the MathML source">Qclass="mathContainer hidden">class="mathCode">$Q$-colourings. Then, using as our main tools the notions of class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15004057&_mathId=si9.gif&_user=111111111&_pii=S0012365X15004057&_rdoc=1&_issn=0012365X&md5=f73088d26ec73f394d9978f89c992c91" title="Click to view the MathML source">Qclass="mathContainer hidden">class="mathCode">$Q$-colourings and class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15004057&_mathId=si16.gif&_user=111111111&_pii=S0012365X15004057&_rdoc=1&_issn=0012365X&md5=03342d9a861e9f6de8debe7c04030e60" title="Click to view the MathML source">Σclass="mathContainer hidden">class="mathCode">$\Sigma$-hypergraphs, we define and prove a result on tight colourings, which is a strengthening of the notion of unique colourability. class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15004057&_mathId=si16.gif&_user=111111111&_pii=S0012365X15004057&_rdoc=1&_issn=0012365X&md5=03342d9a861e9f6de8debe7c04030e60" title="Click to view the MathML source">Σclass="mathContainer hidden">class="mathCode">$\Sigma$-hypergraphs are a natural generalisation of class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15004057&_mathId=si18.gif&_user=111111111&_pii=S0012365X15004057&_rdoc=1&_issn=0012365X&md5=191435a038a52eaea8ce56dee67cb590" title="Click to view the MathML source">σclass="mathContainer hidden">class="mathCode">$\sigma$-hypergraphs introduced by the first two authors in an earlier paper. We also show that there exist class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15004057&_mathId=si16.gif&_user=111111111&_pii=S0012365X15004057&_rdoc=1&_issn=0012365X&md5=03342d9a861e9f6de8debe7c04030e60" title="Click to view the MathML source">Σclass="mathContainer hidden">class="mathCode">$\Sigma$-hypergraphs with arbitrarily large class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15004057&_mathId=si9.gif&_user=111111111&_pii=S0012365X15004057&_rdoc=1&_issn=0012365X&md5=f73088d26ec73f394d9978f89c992c91" title="Click to view the MathML source">Qclass="mathContainer hidden">class="mathCode">$Q$-chromatic number and chromatic number but with bounded clique number. Dvořák et al. have characterised those class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15004057&_mathId=si9.gif&_user=111111111&_pii=S0012365X15004057&_rdoc=1&_issn=0012365X&md5=f73088d26ec73f394d9978f89c992c91" title="Click to view the MathML source">Qclass="mathContainer hidden">class="mathCode">$Q$ which can lead to a hypergraph with a gap in its class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15004057&_mathId=si9.gif&_user=111111111&_pii=S0012365X15004057&_rdoc=1&_issn=0012365X&md5=f73088d26ec73f394d9978f89c992c91" title="Click to view the MathML source">Qclass="mathContainer hidden">class="mathCode">$Q$-spectrum. We give a short direct proof of the necessity of their condition on class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15004057&_mathId=si9.gif&_user=111111111&_pii=S0012365X15004057&_rdoc=1&_issn=0012365X&md5=f73088d26ec73f394d9978f89c992c91" title="Click to view the MathML source">Qclass="mathContainer hidden">class="mathCode">$Q$. We also prove a partial converse for the special case of class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15004057&_mathId=si16.gif&_user=111111111&_pii=S0012365X15004057&_rdoc=1&_issn=0012365X&md5=03342d9a861e9f6de8debe7c04030e60" title="Click to view the MathML source">Σclass="mathContainer hidden">class="mathCode">$\Sigma$-hypergraphs. Finally, we show that, for at least one family class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15004057&_mathId=si9.gif&_user=111111111&_pii=S0012365X15004057&_rdoc=1&_issn=0012365X&md5=f73088d26ec73f394d9978f89c992c91" title="Click to view the MathML source">Qclass="mathContainer hidden">class="mathCode">$Q$ which is known to yield hypergraphs with gaps, there exist no class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15004057&_mathId=si16.gif&_user=111111111&_pii=S0012365X15004057&_rdoc=1&_issn=0012365X&md5=03342d9a861e9f6de8debe7c04030e60" title="Click to view the MathML source">Σclass="mathContainer hidden">class="mathCode">$\Sigma$-hypergraphs with gaps in their class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15004057&_mathId=si9.gif&_user=111111111&_pii=S0012365X15004057&_rdoc=1&_issn=0012365X&md5=f73088d26ec73f394d9978f89c992c91" title="Click to view the MathML source">Qclass="mathContainer hidden">class="mathCode">$Q$-spectrum.