4
$\begingroup$

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)

Improve this question
$\endgroup$
4
  • $\begingroup$ I don't know if this helps, but the asymptotics of the chromatic number for random uniform hypergraphs is known, in a (long!) paper by Krivelevich and Sudakov. $\endgroup$
    – Joseph O'Rourke
    Sep 15, 2010 at 18:36
  • $\begingroup$ @Joseph: thanks, this may prove helpful in the future. I'll take a look at it, but I am interested also in principle in 'non-typical' instances. $\endgroup$
    – Niel de Beaudrap
    Sep 19, 2010 at 12:39
  • $\begingroup$ As you probably realize, this is equivalent to colouring the graph that you get by replacing the hyperedges with cliques. Doing this gives you an upper bound of $k(\omega-1)+1$ if the hypergraph has maximum edge size $\omega$, by Brooks' Theorem. That's a pretty lousy bound, though, and I imagine you can do better. $\endgroup$
    – Andrew D. King
    Sep 19, 2010 at 16:00
  • $\begingroup$ @Andrew: indeed, that construction had occurred to me. In addition to it being lousy, I assumed that anything that any bound that could be achieved by such a simple graph construction was likely to have been surpassed by more sophisticated combinatorial arguments. :-) $\endgroup$
    – Niel de Beaudrap
    Sep 20, 2010 at 6:43

1 Answer 1

Reset to default
4
$\begingroup$

There is a wide variety of hypergraphs for which $k(\omega-1)+1$ is tight or nearly-tight. I also think this is an interesting question, and was looking in to it recently.

First, a $(v, x, 2)$-Steiner system is a partition of the edges of $K_v$ into disjoint $x$-cliques (i.e., each of the $\tbinom{v}{2}$ edges appears in exactly one of the cliques). Whenever $v \ge x^2$, it is known that a $(v', x', 2)$-Steiner system exists where $v' \approx v, x'\approx x$ up to a factor of 2. Then build a hypergraph whose hyperedges are the $x$-cliques. This hypergraph has strong chromatic number $v$ but this actually equals the trivial upper bound of (max degree)(max edge size-1)+1.

Second, for arbitrary max-degree $k>1$ and even edge size $\omega$ there is an elementary example I saw in Agnarsson et al. Take a clique of size $k+1$ and blow up every vertex into a group of $\omega/2$ vertices -- so for every two groups, there is a hyperedge containing them. The strong chromatic number is $(k+1)\omega/2$ which is about half the trivial upper bound.

Eventually I became interested in the following: while the max edge size is a trivial lower bound on the strong chromatic number, the largest clique (set of vertices such that all pairs are contained in a mutual edge) is a larger lower bound (although it's not findable in polynomial time). Can we get good bounds parameterized by the max clique size and the max degree?

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.