Chromatic index of hypergraphs and Shannon's theorem

Let \(G\) be a multigraph without loops and let \(\chi '(G)\) be its chromatic index. A classical theorem of Shannon states that \(\chi '(G)\leq \lfloor \frac{3}{2}\Delta (G)\rfloor \). For a hypergraph \(H\), the 2-section of \(H\) is a multigraph \([H]_{2}\) without loops on the vertex set \(V(H)\), with \(k\) parallel edges between vertices \(u\) and \(v\) (\(u\neq v\)) iff there are \(k\) distinct edges of \(H\), each containing both \(u\) and \(v\). Let \(\Delta (H)\) be the maximum vertex degree in \([H]_{2}\) and \(\chi '(H)\) be the chromatic index of \(H\), i.e. the least number of colors needed to color the edges of \(H\) so that no two intersecting edges have the same color. The author suggests the following generalization of Shannon's theorem to hypergraphs: For any loopless hypergraph \(H\), we have \(\chi '(H)\leq \lfloor \frac{3}{2}\Delta (H)\rfloor \). The conjecture is proved for hypergraphs without repeated edges of size 2.

Recommendations

Cites work

Cited in

(6)

This page was built for publication: Chromatic index of hypergraphs and Shannon's theorem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1580680)