A note on the Erdős--Farber--Lovász conjecture (Q868363): Difference between revisions
From MaRDI portal
Removed claim: author (P16): Item:Q186125 |
ReferenceBot (talk | contribs) Changed an Item |
||
(3 intermediate revisions by 3 users not shown) | |||
Property / author | |||
Property / author: Carol A. Whitehead / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/j.disc.2005.11.053 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2050258148 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3993087 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3360903 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4101818 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5181716 / rank | |||
Normal rank |
Latest revision as of 14:24, 25 June 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