Defective colouring of hypergraphs
We prove that the vertices of every (r + 1)-uniform hypergraph with maximum degree ∆ may be coloured with c( ∆ d+1 ) 1/r colours such that each vertex is in at most d monochromatic edges. This result, which is best possible up to the value of the constant c, generalises the classical result of Erdos...
| Príomhchruthaitheoirí: | , , , |
|---|---|
| Formáid: | Journal article |
| Teanga: | English |
| Foilsithe / Cruthaithe: |
Wiley
2023
|
| Achoimre: | We prove that the vertices of every (r + 1)-uniform hypergraph with maximum degree ∆ may be coloured with c( ∆ d+1 ) 1/r colours such that each vertex is in at most d monochromatic edges. This result, which is best possible up to the value of the constant c, generalises the classical result of Erdos and Lov ˝ asz who proved the ´ d = 0 case. |
|---|