A note on the Erdős--Farber--Lovász conjecture (Q868363): Difference between revisions
From MaRDI portal
Set profile property. |
ReferenceBot (talk | contribs) Changed an Item |
||
(One intermediate revision by one other user not shown) | |||
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 15: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