The chromatic index of simple hypergraphs

A hypergraph \(H=(V,{\mathcal E})\) is called simple if \(| E\cap F| \leq 1\) holds for all pairs of distinct edges, E,F\(\in {\mathcal E}\). A matching in H is a collection of pairwise disjoint edges. The chromatic index of H, denoted by q(H) is the minimum number q such that one can decompose \({\mathcal E}\) into q matchings. The neighborhood of \(x\in V\) is \(N(x)=\cup \{E\setminus \{x\}:\) \(x\in E\in {\mathcal E}\}\) and let \(N(H)=\max_{x\in V}| N(x)|\). In this paper it is proposed the following conjecture: For every simple hypergraph H, \(q(H)\leq N(H)+1\), which is a generalization of Vizing's Theorem. This would imply the Erdős-Faber- Lovász conjecture: q(H)\(\leq | V(H)|\) holds for simple hypergraphs. The author proves also that the above conjecture is true for intersecting hypergraphs: If H is a simple, intersecting hypergraph, i.e., \(| E\cap F| =1\) holds for all pairs of distinct edges E,F\(\in {\mathcal E}(H)\), then \(| {\mathcal E}(H)| \leq N(H)+1\) and equality holds if and only if H is a star with a loop or a near-pencil or a finite projective plane. This conjecture was proposed independently by C. Beye and H. Meyniel.

Recommendations

Cites work

Cited in

(25)

This page was built for publication: The chromatic index of simple hypergraphs

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