Edge coloring of hypergraphs and a conjecture of Erdős, Faber, Lovász
type: Item
instance of: scholarly article
title: Edge coloring of hypergraphs and a conjecture of Erdős, Faber, Lovász
zbMATH Open document ID: 0661.05026
DOI: 10.1007/BF02126801
author: W. I. Chang
author: Eugene L. Lawler
published in: Combinatorica
publication date: 1988-01-01T00:00:00Z
review text: A conjecture of Erdős, Faber, Lovász states that given n sets \(A_ 1,A_ 2,...,A_ n\), with \(| A_ i| =n\) for \(1\leq i\leq n\), and \(| A_ i\cap A_ j| \leq 1\) for \(1\leq i<j\leq n\), one can color the elements of \(\cup A_ i\) with n colors so that for each i no two elements of \(A_ i\) have the same color. Given a hypergraph \(H=(V,E)\), let us define the size of an edge \(e\in E\) as the number of vertices to which e is incident. H is called simple if for any pair u, v of distinct vertices in H there is at most one edge incident to both u and v, and H contains no edges of size one. The conjecture of Erdős, Faber and Lovász is equivalent to the statement that for any simple hypergraph H on n vertices, the chromatic index of H is at most n. In this paper it is proved that for any simple hypergraph H on n vertices, the chromatic index of H is at most \(\lceil 1.5n-2\rceil\), which implies that \(\lceil 1.5n-2\rceil\) colors suffice for the element-coloring problem of Erdős, Faber, Lovász.
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C65
zbMATH DE Number: 4079449
zbMATH Keywords: edge coloring of hypergraphs
zbMATH Keywords: conjecture of Erdős, Faber, Lovász
zbMATH Keywords: simple hypergraph
zbMATH Keywords: chromatic index
Wikidata QID: Q56390927
reviewed by: Ioan Tomescu
MaRDI profile type: Publication
cites work: On the combinatorial problems which I would most like to see solved
cites work: On a Conjecture of Erdös, Faber, and Lovász about n-Colorings
cites work: Packing nearly-disjoint sets
full work available at URL: https://doi.org/10.1007/bf02126801
OpenAlex ID: W2005432897
description: scientific article; zbMATH DE number 4079449