2
$\begingroup$

Let $H$ be a hypergraph of maximum vertex-degree $\Delta$. (That is, for all vertices $x$, we have $| \{ e \in H \mid x \in e \} | \leq \Delta$) Are there any bounds on the chromatic index $\chi_e(H)$ of the form $$ \chi_e(H) \leq c \Delta $$ for some constant $c$?

If not, are there any simple criteria on $H$ that can guarantee this?

Note that if $H$ is a multi-graph, then this follows from Shannon's theorem.

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ Perhaps you know of Alon&Kim, "A note on the degree, size and chromatic index of a uniform hypergraph"? They offer a conjecture that depends on a parameter (the number of shared vertices of any two edges) times $\Delta$, which might suggest there is no constant. (PDF paper download.) $\endgroup$
    – Joseph O'Rourke
    Commented Dec 30, 2015 at 19:20

1 Answer 1

Reset to default
2
$\begingroup$

The answer is definitely no when $c$ is supposed to be independent of number of vertices and size of edges. You can easily construct hypergraphs with an arbitrary number of pairwise intersecting edges and maximum degree $2$.

Improve this answer
$\endgroup$

You must log in to answer this question.

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