Edge coloring of hypergraphs and a conjecture of Erdős, Faber, Lovász (Q1112832)

From MaRDI portal
Revision as of 10:47, 30 July 2024 by Openalex240730090724 (talk | contribs) (Set OpenAlex properties.)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
scientific article
Language Label Description Also known as
English
Edge coloring of hypergraphs and a conjecture of Erdős, Faber, Lovász
scientific article

    Statements

    Edge coloring of hypergraphs and a conjecture of Erdős, Faber, Lovász (English)
    0 references
    0 references
    0 references
    1988
    0 references
    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.
    0 references
    edge coloring of hypergraphs
    0 references
    conjecture of Erdős, Faber, Lovász
    0 references
    simple hypergraph
    0 references
    chromatic index
    0 references
    0 references

    Identifiers