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
    Commented 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
    Commented 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
    Commented 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
    Commented 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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .