Name
Abstract | ||
|---|---|---|
We look at colourings of r -uniform hypergraphs, focusing our attention on unique colourability and gaps in the chromatic spectrum. The pattern of an edge E in an r -uniform hypergraph H whose vertices are coloured is the partition of r induced by the colour classes of the vertices in E . Let Q be a set of partitions of r . A Q -colouring of H is a colouring of its vertices such that only patterns appearing in Q are allowed. We first show that many known hypergraph colouring problems, including Ramsey theory, can be stated in the language of Q -colourings. Then, using as our main tools the notions of Q -colourings and Σ -hypergraphs, we define and prove a result on tight colourings, which is a strengthening of the notion of unique colourability. Σ -hypergraphs are a natural generalisation of ¿ -hypergraphs introduced by the first two authors in an earlier paper. We also show that there exist Σ -hypergraphs with arbitrarily large Q -chromatic number and chromatic number but with bounded clique number. Dvořák et¿al. have characterised those Q which can lead to a hypergraph with a gap in its Q -spectrum. We give a short direct proof of the necessity of their condition on Q . We also prove a partial converse for the special case of Σ -hypergraphs. Finally, we show that, for at least one family Q which is known to yield hypergraphs with gaps, there exist no Σ -hypergraphs with gaps in their Q -spectrum. |
Year | DOI | Venue |
|---|---|---|
2016 | 10.1016/j.disc.2015.11.006 | Discrete Mathematics |
Keywords | Field | DocType |
hypergraphs | Ramsey theory,Converse,Discrete mathematics,Combinatorics,Vertex (geometry),Constraint graph,Hypergraph,Partition (number theory),Mathematics,Bounded function,Direct proof | Journal |
Volume | Issue | ISSN |
339 | 4 | 0012-365X |
Citations | PageRank | References |
0 | 0.34 | 10 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Yair Caro | 1 | 406 | 84.73 |
| josef lauri | 2 | 32 | 10.71 |
| christina zarb | 3 | 4 | 3.22 |