Single conflict coloring and palette sparsification of uniform hypergraphs
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912817310859264 |
|---|---|
| author | Casselgren, Carl Johan Eriksson, Kalle |
| author_facet | Casselgren, Carl Johan Eriksson, Kalle |
| contents | We introduce and investigate single conflict coloring in the setting of r-uniform hypergraphs. We establish some basic properties of this hypergraph coloring model and study a probabilistic model of single conflict coloring where the conflicts for each edge are chosen randomly; in particular, we prove a sharp threshold-type result for complete graphs and establish a sufficient condition for single conflict colorability of r-uniform hypergraphs in this model. Furthermore, we obtain a related palette sparsification-type result for general list coloring of linear uniform hypergraphs (i.e. uniform hypergraphs where any two edges share at most one common vertex). Throughout the paper we pose several questions and conjectures |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2601_06990 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Single conflict coloring and palette sparsification of uniform hypergraphs Casselgren, Carl Johan Eriksson, Kalle Combinatorics We introduce and investigate single conflict coloring in the setting of r-uniform hypergraphs. We establish some basic properties of this hypergraph coloring model and study a probabilistic model of single conflict coloring where the conflicts for each edge are chosen randomly; in particular, we prove a sharp threshold-type result for complete graphs and establish a sufficient condition for single conflict colorability of r-uniform hypergraphs in this model. Furthermore, we obtain a related palette sparsification-type result for general list coloring of linear uniform hypergraphs (i.e. uniform hypergraphs where any two edges share at most one common vertex). Throughout the paper we pose several questions and conjectures |
| title | Single conflict coloring and palette sparsification of uniform hypergraphs |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2601.06990 |