Chromatic index of hypergraphs and Shannon's theorem
type: Item
instance of: scholarly article
title: Chromatic index of hypergraphs and Shannon's theorem
zbMATH Open document ID: 0963.05052
author: Tomáš Dvořák
published in: European Journal of Combinatorics
publication date: 2001-06-21T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C65
zbMATH DE Number: 1512041
zbMATH Keywords: chromatic index
zbMATH Keywords: hypergraph
zbMATH Keywords: generalized Shannon theorem
reviewed by: Fedor V. Fomin
MaRDI profile type: Publication
full work available at URL: eujc.1999.0388
OpenAlex ID: W2139417620
cites work: An application of matching theory of edge-colourings
cites work: Q3993087
cites work: Q3348010
cites work: A short proof for a generalization of Vizing's theorem
cites work: Edge coloring of hypergraphs and a conjecture of Erdős, Faber, Lovász
cites work: Q5181716
cites work: The chromatic index of simple hypergraphs
cites work: On a Conjecture of Erdös, Faber, and Lovász about n-Colorings
cites work: Coloring nearly-disjoint hypergraphs with \(n + o(n)\) colors
cites work: Q3880849
cites work: Asymptotic behavior of the chromatic index for hypergraphs
cites work: A Theorem on Coloring the Lines of a Network
DOI: 10.1006/EUJC.1999.0388
description: scientific article; zbMATH DE number 1512041