Skip to main content
5 of 5
replaced http://cstheory.stackexchange.com/ with https://cstheory.stackexchange.com/

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)