Defective coloring of hypergraphs

António Girão; Freddie Illingworth; Alex Scott; David R. Wood

doi:10.1002/rsa.21190

Defective coloring of hypergraphs

António Girão, Freddie Illingworth, Alex Scott, David R. Wood

School of Mathematics

Research output: Contribution to journal › Article › Research › peer-review

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.

Original language	English
Pages (from-to)	663-675
Number of pages	13
Journal	Random Structures and Algorithms
Volume	64
Issue number	3
DOIs	https://doi.org/10.1002/rsa.21190
Publication status	Published - May 2023

Keywords

coloring
hypergraphs
Lovász local lemma

Access to Document

10.1002/rsa.21190Licence: CC BY

Cite this

@article{6caa13931ff5479baafa908912635f50,

title = "Defective coloring of hypergraphs",

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{\H o}s and Lov{\'a}sz who proved the (Formula presented.) case.",

keywords = "coloring, hypergraphs, Lov{\'a}sz local lemma",

author = "Ant{\'o}nio Gir{\~a}o and Freddie Illingworth and Alex Scott and Wood, {David R.}",

note = "Funding Information: Research supported by EPSRC Grant EP/V007327/1. Research supported by the Australian Research Council and a Visiting Research Fellowship of Merton College, University of Oxford. Publisher Copyright: {\textcopyright} 2023 The Authors. Random Structures & Algorithms published by Wiley Periodicals LLC.",

year = "2023",

month = may,

doi = "10.1002/rsa.21190",

language = "English",

volume = "64",

pages = "663--675",

journal = "Random Structures and Algorithms",

issn = "1042-9832",

publisher = "John Wiley & Sons",

number = "3",

}

TY - JOUR

T1 - Defective coloring of hypergraphs

AU - Girão, António

AU - Illingworth, Freddie

AU - Scott, Alex

AU - Wood, David R.

N1 - Funding Information: Research supported by EPSRC Grant EP/V007327/1. Research supported by the Australian Research Council and a Visiting Research Fellowship of Merton College, University of Oxford. Publisher Copyright: © 2023 The Authors. Random Structures & Algorithms published by Wiley Periodicals LLC.

PY - 2023/5

Y1 - 2023/5

N2 - 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.

AB - 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.

KW - coloring

KW - hypergraphs

KW - Lovász local lemma

UR - http://www.scopus.com/inward/record.url?scp=85175090356&partnerID=8YFLogxK

U2 - 10.1002/rsa.21190

DO - 10.1002/rsa.21190

M3 - Article

AN - SCOPUS:85175090356

SN - 1042-9832

VL - 64

SP - 663

EP - 675

JO - Random Structures and Algorithms

JF - Random Structures and Algorithms

IS - 3

ER -

Defective coloring of hypergraphs

Abstract

Keywords

Access to Document

Other files and links

Cite this