Chromatic index of simple hypergraphs

DOI10.1016/J.DISC.2020.112087MaRDI QIDQ2005680zbMATH OpenOpenAlexFDO

Authors Guo-Hui Zhang, Brett Skinner

Publication date 8 October 2020

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.disc.2020.112087

zbMATH Keywords

chromatic indexsimple hypergraphs

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Hypergraphs (05C65)

Review text

The authors consider the problem of edge coloring of simple hypergraphs. There is a very well-known conjecture given independly by \textit{C. Berge} [in: Combinatorial mathematics, Proc. 3rd Int. Conf., New York/ NY (USA) 1985, Ann. N. Y. Acad. Sci. 555, 40--44 (1989; Zbl 0726.05055)] and \textit{Z. Füredi} [Graphs Comb. 2, 89--92 (1986; Zbl 0589.05036)]. It says that \(\chi^\prime(H)\leq \Delta(H)+1\) for any simple hypergraph \(H\). The authors prove this conjecture for simple hypergraphs of degree at most 5. Moreover, they give a new upper bound on the chromatic index of the hypergraph \(H\), namely \(\chi^\prime(H)\leq \frac{7}{4}\Delta(H) - 1\). The paper gives a very nice contribution to the problem of hyperedge coloring.

Recommendations

• The chromatic index of simple hypergraphs
• The chromatic index of complete multipartite graphs
• Acyclic chromatic index of chordless graphs
• Chromatic index of hypergraphs and Shannon's theorem
• The chromatic index of strongly regular graphs
• The chromatic distinguishing index of certain graphs
• On the chromatic index of almost all graphs
• On chromaticity of hypergraphs
• scientific article; zbMATH DE number 4187830
• The \(b\)-chromatic index of graphs

Cites work

• A short proof for a generalization of Vizing's theorem
• A Theorem on Coloring the Lines of a Network
• Asymptotic behavior of the chromatic index for hypergraphs
• Chromatic index of hypergraphs and Shannon's theorem
• Coloring nearly-disjoint hypergraphs with \(n + o(n)\) colors
• Edge coloring of hypergraphs and a conjecture of Erdős, Faber, Lovász
• scientific article; zbMATH DE number 4198041 (Why is no real title available?)
• scientific article; zbMATH DE number 3523543 (Why is no real title available?)
• scientific article; zbMATH DE number 3428958 (Why is no real title available?)
• Matching theory
• On a Conjecture of Erdös, Faber, and Lovász about n-Colorings
• The chromatic index of simple hypergraphs

Cited in

(17)

• The chromatic index of simple hypergraphs
• Edge coloring of hypergraphs and a conjecture of Erdős, Faber, Lovász
• Coloring nearly-disjoint hypergraphs with \(n + o(n)\) colors
• On conjectures of Berge and Chvátal
• A generalization of chromatic index
• Chromatic index of hypergraphs and Shannon's theorem
• The list chromatic index of simple graphs whose odd cycles intersect in at most one edge
• The Erdős-Faber-Lovász conjecture for dense hypergraphs
• scientific article; zbMATH DE number 4198041 (Why is no real title available?)
• scientific article; zbMATH DE number 4214033 (Why is no real title available?)
• scientific article; zbMATH DE number 4214051 (Why is no real title available?)
• scientific article; zbMATH DE number 25252 (Why is no real title available?)
• Grünbaum colorings extended to non-facial 3-cycles
• Solution to a problem of Erdős on the chromatic index of hypergraphs with bounded codegree
• About Berge-Füredi's conjecture on the chromatic index of hypergraphs
• Asymptotic behavior of the chromatic index for hypergraphs
• A note on the Erdős--Farber--Lovász conjecture

This page was built for publication: Chromatic index of simple hypergraphs

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