Skip to main content
4 of 5
Completely rephrased in what are hopefully equivalent terms

Bounds on strong vertex colourings of regular hypergraphs?

What are the best results for upper bounds on the number of colours required in a strong vertex colouring of a regular hypergraph H?

  • A regular hypergraph is one in which every vertex is contained in k edges, for some constant k. (The edges may contain more than two vertices, and may contain different numbers of vertices from each other.)

  • A strong vertex colouring is one in which, for each edge, every vertex contained in that edge has a different colour.

I am hoping for an upper bound formulated in terms of the degree k of the vertices, the maximum cardinality of any edge, and other graph parameters — but without imposing any restrictions on the hypergraphs, aside possibly from a bound on edge cardinality. I would be especially interested in constructive proofs (i.e. ones which describe algorithms, or at least randomized constructions with high probability of success).

[Note. This question originally asked about edge-chromatic numbers in uniform hypergraphs, which is an equivalent problem. I have substantially shortened this question, and rephrased it in the form above, in the hopes that I might answers using a different presentation.]

(Related question on the CSTheory StackExchange site)