Skip to Main content Skip to Navigation
New interface
Journal articles

On hyperedge coloring of weakly trianguled hypergraphs and well ordered hypergraphs

Alain Bretto 1 Alain Faisant 2 François Hennecart 3 
1 Equipe CODAG - Laboratoire GREYC - UMR6072
GREYC - Groupe de Recherche en Informatique, Image et Instrumentation de Caen
3 CTN - Combinatoire, théorie des nombres
ICJ - Institut Camille Jordan [Villeurbanne]
Abstract : A well-known conjecture of Erdős, Faber and Lovász can be stated in the following way: every loopless linear hypergraph H on n vertices can be n-edge-colored, or equivalently q(H) ≤ n, where q(H) is the chromatic index of H , i.e. the smallest number of colors such that intersecting hyperedges of H are colored with distinct colors. In this article we prove this assertion for Helly hypergraphs, for weakly trianguled hypergraphs, for well ordered hypergraphs and for a certain family of uniform hypergraphs.
Document type :
Journal articles
Complete list of metadata

https://hal.archives-ouvertes.fr/hal-02933032
Contributor : Accord Elsevier CCSD Connect in order to contact the contributor
Submitted on : Monday, August 22, 2022 - 1:58:38 PM
Last modification on : Saturday, September 24, 2022 - 3:36:05 PM
Long-term archiving on: : Wednesday, November 23, 2022 - 10:21:57 PM

File

S0012365X20302454.pdf
Files produced by the author(s)

Licence


Distributed under a Creative Commons Attribution - NonCommercial 4.0 International License

Identifiers

Citation

Alain Bretto, Alain Faisant, François Hennecart. On hyperedge coloring of weakly trianguled hypergraphs and well ordered hypergraphs. Discrete Mathematics, 2020, 343, ⟨10.1016/j.disc.2020.112059⟩. ⟨hal-02933032⟩

Share

Metrics

Record views

42

Files downloads

3