Edge-coloring linear hypergraphs with medium-sized edges

DOI10.1002/RSA.20843MaRDI QIDQ5236928zbMATH OpenOpenAlexFDO

Authors Vance Faber, David G. Harris

Publication date 16 October 2019

Published in Random Structures \& Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1707.08372

zbMATH Keywords

chromatic indexEFLlinear hypergraph

Mathematics Subject Classification ID

Distance in graphs (05C12) Coloring of graphs and hypergraphs (05C15) Hypergraphs (05C65)

Abstract: Motivated by the ErdH{o}s-Faber-Lov'{a}sz (EFL) conjecture for hypergraphs, we consider the list edge coloring of linear hypergraphs. We show that if the hyper-edge sizes are bounded between $i$ and $C_{i,epsilon}sqrtn$ inclusive, then there is a list edge coloring using $(1+epsilon)fracni-1$ colors. The dependence on $n$ in the upper bound is optimal (up to the value of $C_{i,epsilon}$).

Recommendations

• On edge coloring of hypergraphs and Erdős-Faber-Lovász conjecture
• On hyperedge coloring of weakly trianguled hypergraphs and well ordered hypergraphs
• Edge coloring of hypergraphs and a conjecture of Erdős, Faber, Lovász
• Near-optimal list colorings
• scientific article; zbMATH DE number 4214051

Cites work

• A General Upper Bound on the List Chromatic Number of Locally Sparse Graphs
• Advances on the Erdős-Faber-Lovász conjecture
• Asymptotically good list-colorings
• Coloring graphs with sparse neighborhoods
• Coloring nearly-disjoint hypergraphs with \(n + o(n)\) colors
• The Erdős-Faber-Lovász conjecture for dense hypergraphs

Cited in

(6)

• Coloring linear hypergraphs: the Erdős-Faber-Lovász conjecture and the combinatorial nullstellensatz
• Graph theory. Abstracts from the workshop held January 2--8, 2022
• A note on edge coloring of linear hypergraphs
• Graph and hypergraph colouring via nibble methods: a survey
• A proof of the Erdős-Faber-Lovász conjecture
• A note on the Berge-Meyniel conjecture

This page was built for publication: Edge-coloring linear hypergraphs with medium-sized edges

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