A note on the Erdős--Farber--Lovász conjecture (Q868363): Difference between revisions
From MaRDI portal
Changed an Item |
Set profile property. |
||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank |
Revision as of 02:26, 5 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A note on the Erdős--Farber--Lovász conjecture |
scientific article |
Statements
A note on the Erdős--Farber--Lovász conjecture (English)
0 references
2 March 2007
0 references
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\).
0 references
hypergraph
0 references
edge-coloring
0 references