Single conflict coloring and palette sparsification of uniform hypergraphs This paper is partially based on the thesis written by the second author under the supervision of the first author
Carl Johan Casselgren, Kalle Eriksson · 2026
Read Single conflict coloring and palette sparsification of uniform hypergraphs This paper is partially based on the thesis written by the second author under the supervision of the first author by Carl Johan Casselgren, Kalle Eriksson (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-06990.txt.
Introduction
Carl Johan Casselgren and co-authors published a 2026 arXiv preprint. The preprint covers single conflict coloring and palette sparsification of uniform hypergraphs this paper is partially. It appeared in the arXiv PAPERS collection for 2026. The authors introduce and investigate single conflict coloring in the setting of r 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 r -uniform hypergraphs in this model. The preprint gives researchers a focused account of the problem and the approach the authors take.
Catalog record
| CREATOR | Carl Johan Casselgren, Kalle Eriksson |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 48 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2601-06990
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Single conflict coloring and palette sparsification of uniform hypergraphs This paper is partially based on the thesis written by the second author under the supervision of the first author Carl Johan Casselgren, Kalle Eriksson Abstract We introduce and investigate single conflict coloring in the setting of r 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 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. Keywords: Hypergraph coloring; Single conflict coloring; Palette sparsification Mathematics Subject Classification: 05C15 1 Introduction Being first introduced in the 70’s [ 24 , 47 ] , list coloring is a well-established area of hypergraph coloring. Formally, given a hypergraph G , we assign to each vertex v of G a set L(v) of colors; L is called a list assignment for G and the sets L(v) are referred to as lists or color lists . If there is a proper coloring \varphi of G (i.e. no edge is monochromatic) such that \varphi(v)\in L(v) for all v\in V(G) , then G is L -colorable and \varphi is called an L -coloring or simply a list coloring . Furthermore, G is called k -choosable if it is L -colorable for every list assignment L where all lists have size at least k . The minimum k such that G is k -choosable is the list-chromatic number (or choice number ) \mathrm{ch}(G) of G . Many hypergraph coloring models translate naturally to the list coloring setting, and numerous variants of list coloring are studied in the literature. Our primary interest here, single conflict coloring , is a generalization of several other (hyper-)graph list coloring invariants, so let us begin by briefly reviewing some related coloring models. Given an edge coloring f of a hypergraph G , a coloring c:V(G)\to\mathbf{Z} is adapted to f if no edge e satisfies that every vertex contained in e has the the color f(e) under c . Adapted coloring was introduced by Hell and Zhu [ 30 ] , who among other things proved that a graph is adaptably 2 -colorable if and only if it contains an edge whose removal yields a bipartite graph. They also proved general bounds on the adaptable chromatic number \chi_{a}(G) , that is, the least number of colors needed for an adaptable coloring of a graph G . Building on the notion of adaptable coloring, Kostochka and Zhu [ 37 ] considered the list coloring version of adaptable coloring for graphs and hypergraphs, where the vertices are assigned lists, and we seek a list coloring that is adapted to a given edge coloring. The minimum size of the lists which ensures the existence of such an adapted list coloring is the adaptable choice number \mathrm{ch}_{ad}(G) (or adaptable choosability ) of a hypergraph G . Kostochka and Zhu proved a general upper bound on this invariant and also characterized graphs with adaptable choosability 2 . Another variant of list coloring is so-called choosability with separation, introduced by Kratochvil, Tuza and Voigt [ 38 ] . In this model, we require that color lists of vertices contained in a common edge have bounded intersection, and ask for the minimum size of the lists which guarantees existence of a proper list coloring of the hypergraph in question. Single conflict coloring is related to the variant where lists of vertices contained in a common edge have at most one common color, often referred to as separation choosability . Denote by \mathrm{ch}_{sep}(G) the smallest size of the lists which ensure that G is colorable from such lists, provided that lists of vertices contained in a common edge intersect in at most one color. This particular variant was specifically studied in e.g. [ 26 , 28 ] . Generalizing both the notion of adaptable choosability and separation choosability [ 38 ] , single conflict coloring of graphs was introduced by Dvorak et al. [ 21 ] . A local k -partition of a graph G is a collection \{c_{v}\}_{v\in V(G)} of maps c_{v}:E(v)\to\{1,\dots,k\} , where E(v) denotes the set of edges incident with v . We think of c as a conflict map, and for each edge e=xy\in E(G) , c yields a conflict-pair (c_{x}(e),c_{y}(e)) . Given such a local k -partition \{c_{v}\} , G is conflict \{c_{v}\} -colorable if there is a map \varphi:V(G)\to\{1,\dots,k\} such that no edge e=xy satisfies that \varphi(x)=c_{x}(e) and \varphi(y)=c_{y}(e) . The single conflict chromatic number \chi_{\nleftrightarrow}(G) of G is the smallest k such that G is conflict \{c_{v}\} -colorable for every local k -partition \{c_{v}\} . Dvorak and Postle [ 22 ] introduced correspondence coloring (also known as DP-coloring) as a generalization of list coloring. Roughly, the idea is to replace every vertex v in a hypergraph G by a set I_{v} of k isolated vertices, and to replace every edge of G by a (hyper-)matching. (The vertices in the added independent sets correspond to the colors in a list of size k .) If there is a transversal (i.e. an independent set intersecting each I_{v} in exactly one vertex) in the resulting hypergraph for any choice of the matchings joining independent sets, then the graph is k -DP-colorable . The DP-chromatic number \chi_{DP}(G) is the minimum k such that G is k -DP-colorable 1 1 1 See [ 46 ] for a formal definition. . In this paper we introduce and study single conflict coloring in the setting of r -uniform hypergraphs. 2 2 2 A formal definition is given at the beginning of Section 2. We establish some basic properties and relate the single conflict chromatic number to other hypergraph coloring invariants. In particular, based on a construction in [ 37 ] , for every pair of integers r,d , we give an example of an r -uniform hypergraph H_{r,d} such that \mathrm{ch}(H_{r,d})=\mathrm{ch}_{sep}(H_{r,d})=\mathrm{ch}_{ad}(H_{r,d})=\chi_{\nleftrightarrow}(H_{r,d})=\chi_{DP}(H_{r,d})=d. Next, inspired by the probabilistic model of DP-coloring of graphs from random covers studied in [ 8 ] , we consider a random model of single conflict coloring of r -uniform hypergraphs, which we define formally in Section 3. As in [ 8 ] we analyze the probability of the existence of a single conflict coloring in terms of degeneracy; we also prove a sharp threshold type result for complete graphs, and conjecture that an analogous statement is true for complete r -uniform hypergraphs. Finally, we consider the related problem of palette sparsification of ordinary list coloring of r -uniform hypergraphs. Assadi, Chen, and Khanna [ 6 ] recently proved that for every n -vertex graph G with maximum degree \Delta , sampling O(\log n) colors for each vertex independently from \Delta+1 colors suffices for ensuring the existence of a proper coloring of G from the sampled colors with probability tending to 1 as n\to\infty . This palette sparsification result has received considerable