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)

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)

What are the best results for upper bounds on the edge-chromatic χ'(H) number of k-uniform hypergraphs H?

• A k-uniform hypergraph is one in which every edge contains precisely k vertices.
• A proper edge colouring, as usual, is one in which edges of the same colour are disjoint.

I'm actually interested in principle in results for labelled k-uniform hypergraphs, where two edges may actually have the same edge set; but I would also be interested in results where edges must have distinct vertex-sets.

There seem to be several results around with added restrictions (the number of edges being small; the intersection size of edges being bounded above by a constant, etc.), but the only additional restrictions I would be interested in would be degree bounds, e.g. Δ(H) < f(k) for some strictly monotonic function f. (Equivalently, taking the dual hypergraph, I would also be interested in strong vertex colouring results for k-regular hypergraphs, but which are not necessarily uniform --- perhaps with monotonically increasing bounds on the cardinality of the edges in terms of other parameters, but without additional restrictions.)

In this setting, what are the best known upper bounds on χ'(H), expressed in terms of the hypergraph size (the number of vertices and/or edges), the maximum degree, and other such basic structural properties?

I would be especially interested in constructive proofs (i.e. ones which describe algorithms, or at least randomized constructions with high probability of success).

(Related question on the CSTheory StackExchange site)

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)

What are the best results for upper bounds on the edge-chromatic χ'(H) number of k-uniform hypergraphs H?

• A k-uniform hypergraph is one in which every edge contains precisely k vertices.
• A proper edge colouring, as usual, is one in which edges of the same colour are disjoint.

I'm actually interested in principle in results for labelled k-uniform hypergraphs, where two edges may actually have the same edge set; but I would also be interested in results where edges must have distinct vertex-sets.

There seem to be several results around with added restrictions (the number of edges being small; the intersection size of edges being bounded above by a constant, etc.), but the only additional restrictions I would be interested in would be degree bounds, e.g. Δ(H) < f(k) for some strictly monotonic function f. (Equivalently, taking the dual hypergraph, I would also be interested in strong vertex colouring results for k-regular hypergraphs, but which are not necessarily uniform. Perhaps there are monotonically increasing bounds on the cardinality of the edges in terms of other parameters, but there are not other additional restrictions.)

In this setting, what are the best known upper bounds on χ'(H), expressed in terms of the hypergraph size (the number of vertices and/or edges), the maximum degree, and other such basic structural properties?

I would be especially interested in constructive proofs (i.e. ones which describe algorithms, or at least randomized constructions with high probability of success).

(Related question on the CSTheory StackExchange site)

What are the best results for upper bounds on the edge-chromatic χ'(H) number of k-uniform hypergraphs H?

• A k-uniform hypergraph is one in which every edge contains precisely k vertices.
• A proper edge colouring, as usual, is one in which edges of the same colour are disjoint.

I'm actually interested in principle in results for labelled k-uniform hypergraphs, where two edges may actually have the same edge set; but I would also be interested in results where edges must have distinct vertex-sets.

There seem to be several results around with added restrictions (the number of edges being small; the intersection size of edges being bounded above by a constant, etc.), but the only additional restrictions I would be interested in would be degree bounds, e.g. Δ(H) < f(k) for some strictly monotonic function f. (Equivalently, taking the dual hypergraph, I would also be interested in strong vertex colouring results for k-regular hypergraphs, but which are not necessarily uniform --- perhaps with monotonically increasing bounds on the cardinality of the edges in terms of other parameters, but without additional restrictions.)

In this setting, what are the best known upper bounds on χ'(H), expressed in terms of the hypergraph size (the number of vertices and/or edges), the maximum degree, and other such basic structural properties?

I would be especially interested in constructive proofs (i.e. ones which describe algorithms, or at least randomized constructions with high probability of success).

(Related question on the CSTheory StackExchange site)