A note on the Erdős--Farber--Lovász conjecture (Q868363): Difference between revisions

A hypergraph \(H=(V(H), E(H))\) is simple if \(| e\cap f| \leq 1\) for all distinct edges \(e, f\in E(H)\) and each edge consists of at least two vertices. \(\Delta_H=\max_{v\in V(H)}| \{e \mid v\in e, e\in E(H)\}| \) is the maximum degree of \(H\). A \(k\)-edge coloring of \(H\) is an assignment of \(k\) colors to the edges of \(H\) so that distinct intersecting edges receive different colors. The chromatic index \(q(H)\) of \(H\) is the last number \(k\) of colors required for a \(k\)-edge coloring of \(H\). The authors reformulate a well-known conjecture due to Erdős, Farber and Lovász on vertex coloring of hypergraphs to the following conjecture: For all simple hypergraphs \(H\) on \(n\) vertices, \(q(H)\leq n\). They then prove this conjecture for the case when the partial hypergraph \(H'\) of \(H\) determined by the edges of size at least three satisfies \(q(H')=\Delta_{H'}\leq 3\). In particular, the conjecture is true when \(H'\) is unimodular and \(\Delta_{H'}\leq 3\).