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.

$\endgroup$
  • 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 Dec 30 '15 at 19:20
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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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