Defective coloring of hypergraphs

DOI10.1002/RSA.21190MaRDI QIDQ6201037zbMATH OpenOpenAlexFDO

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

Publication date 25 March 2024

Published in Random Structures \& Algorithms (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2207.10514

zbMATH Keywords

Lovász local lemma\((r+1)\)-uniform hypergraphsgrah coloring

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Hypergraphs (05C65)

Abstract: We prove that the vertices of every $(r+1)$-uniform hypergraph with maximum degree $Delta$ may be coloured with $c(fracDeltad+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 ErdH{o}s and Lov'asz who proved the $d=0$ case.

Recommendations

• Defective colorings on k-uniform hypergraphs
• scientific article; zbMATH DE number 5825874
• Colorings of hypergraphs with large number of colors
• Coloring sparse hypergraphs
• On proper colorings of hypergraphs

Cites work

• scientific article; zbMATH DE number 4170917 (Why is no real title available?)
• scientific article; zbMATH DE number 3492718 (Why is no real title available?)
• scientific article; zbMATH DE number 3243267 (Why is no real title available?)
• scientific article; zbMATH DE number 3198427 (Why is no real title available?)
• A general framework for hypergraph coloring
• A relative of Hadwiger's conjecture
• Coding for Sunflowers
• Coloring H-free hypergraphs
• Coloring sparse hypergraphs
• Coloring uniform hypergraphs with few edges
• Conflict-free colourings of uniform hypergraphs with few edges
• Constructive proofs of concentration bounds
• Defective and clustered graph colouring
• Improper colourings inspired by Hadwiger's conjecture
• Improved bounds for the sunflower lemma
• Intersection Theorems for Systems of Sets
• Judicious \(k\)-partitions of graphs
• Judicious partitions and related problems
• Judicious partitions of bounded‐degree graphs
• Judicious partitions of uniform hypergraphs
• List coloring triangle-free hypergraphs
• Max \(k\)-cut and judicious \(k\)-partitions
• Maximum cuts and judicious partitions in graphs without short cycles
• Note on sunflowers
• On judicious partitions of hypergraphs with edges of size at most 3
• On judicious partitions of uniform hypergraphs
• Partitions of hypergraphs under variable degeneracy constraints
• Problems and results on judicious partitions
• Randomly coloring simple hypergraphs
• Sparse hypergraphs with low independence number
• Thresholds versus fractional expectation-thresholds

This page was built for publication: Defective coloring of hypergraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6201037)