5
$\begingroup$

A proper $k$-edge-coloring of a hypergraph $H$ is a mapping from $E(H)$ to a set of $k$ colors so that every pair of adjacent edges receives different colors. We say $H$ is $k$-edge-colorable if $H$ has a proper $k$-edge-coloring. The chromatic index of $H$, denoted $\chi'(H)$, is the least $k$ such that $H$ is $k$-edge colorable.

If $H$ is a 2-uniform hypergraph, then by Vizing's theorem, $\chi'(H)\leq \Delta(H)+1$. Furthermore, if $H$ is a $k$-uniform hypergraph, it is easy to see that $\chi'(H)\leq k(\Delta(H)-1)+1$ by greedly coloring the edges.

Now, is there any better known bound for $\chi'(H)$ if $H$ is a $k$-uniform hypergraph, for any integer $k$?

Improve this question
$\endgroup$
5
  • $\begingroup$ By adjacent edges you mean intersecting edges? $\endgroup$
    – Fedor Petrov
    Commented Nov 18, 2021 at 10:02
  • 1
    $\begingroup$ This question is studied a lot, but as far as I know better bounds in full generality are not proved even for $k=3$, see for instance doi.org/10.1016/j.dam.2016.06.009 $\endgroup$
    – Fedor Petrov
    Commented Nov 18, 2021 at 10:17
  • $\begingroup$ Yes, by adjacent edges I mean intersecting edges. $\endgroup$
    – W. Paul Liu
    Commented Nov 18, 2021 at 10:50
  • 2
    $\begingroup$ This doesn't sound like the case you are interested in, but when $\Delta(H)\leq (1-o(1))t|V(G)|$ with $t\geq 2$, Kang, Kelly, K\"uhn, Methuku, and Osthus proved that the chromatic index is at most $t|V(G)|$ (and thus at most $(1+o(1))\Delta(H)$) under the additional assumption that the co-degree is at most $t$. arxiv.org/pdf/2110.06181.pdf This is a generalization of the Erd\H{o}s, Faber, Lov\'asz conjecture (which they also recently proved). $\endgroup$
    – Louis D
    Commented Nov 18, 2021 at 15:21
  • $\begingroup$ Sorry, in my above comment, change the $G$'s to $H$'s. $\endgroup$
    – Louis D
    Commented Nov 18, 2021 at 17:52

0

Reset to default

You must log in to answer this question.