Girao, Antonio;
Illingworth, Freddie;
Scott, Alex;
Wood, David R;
(2023)
Defective coloring of hypergraphs.
Random Structures and Algorithms
10.1002/rsa.21190.
(In press).
Preview |
Text
defective_col_RSA.pdf - Published Version Download (1MB) | Preview |
Abstract
We prove that the vertices of every (Formula presented.) -uniform hypergraph with maximum degree (Formula presented.) may be colored with (Formula presented.) colors such that each vertex is in at most (Formula presented.) monochromatic edges. This result, which is best possible up to the value of the constant (Formula presented.), generalizes the classical result of Erdős and Lovász who proved the (Formula presented.) case.
| Type: | Article |
|---|---|
| Title: | Defective coloring of hypergraphs |
| Open access status: | An open access version is available from UCL Discovery |
| DOI: | 10.1002/rsa.21190 |
| Publisher version: | http://dx.doi.org/10.1002/rsa.21190 |
| Language: | English |
| Additional information: | © 2023 The Authors. Random Structures & Algorithms published by Wiley Periodicals LLC. This is an open access article under the terms of the Creative Commons Attribution License, which permits use, distribution and reproduction in any medium, provided the original work is properly cited. |
| Keywords: | Science & Technology, Technology, Physical Sciences, Computer Science, Software Engineering, Mathematics, Applied, Mathematics, Computer Science, coloring, hypergraphs, Lovasz local lemma, JUDICIOUS PARTITIONS |
| UCL classification: | UCL UCL > Provost and Vice Provost Offices > UCL BEAMS UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Maths and Physical Sciences UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Maths and Physical Sciences > Dept of Mathematics |
| URI: | https://discovery-pp.ucl.ac.uk/id/eprint/10189635 |
Archive Staff Only
 |
View Item |
