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.
scientific article; zbMATH DE number 1512041
scientific article