TY - JOUR

T1 - Conflict-Free Colouring of Subsets

AU - Jartoux, Bruno

AU - Keller, Chaya

AU - Smorodinsky, Shakhar

AU - Yuditsky, Yelena

N1 - Publisher Copyright:
© The Author(s), under exclusive licence to Springer Science+Business Media, LLC, part of Springer Nature 2023.

PY - 2024/9

Y1 - 2024/9

N2 - We introduce and study conflict-free colourings of t-subsets in hypergraphs. In such colourings, one assigns colours to all subsets of vertices of cardinality t such that in any hyperedge of cardinality at least t there is a uniquely coloured t-subset. The case t=1, i.e., vertex conflict-free colouring, is a well-studied notion that originates in the context of frequency allocation to antennas in cellular networks. It has caught the attention of researchers both from the combinatorial and algorithmic points of view. A special focus was given to hypergraphs arising in geometry. Already the case t=2 (i.e., colouring pairs) seems to present a new challenge. Many of the tools used for conflict-free colouring of geometric hypergraphs rely on hereditary properties of the underlying hypergraphs. When dealing with subsets of vertices, the properties do not pass to subfamilies of subsets. Therefore, we develop new tools, which might be of independent interest. For any fixed t, we show that the ntt-subsets in any set P of n points in the plane can be coloured with O(t2log2n) colours so that any axis-parallel rectangle that contains at least t points of P also contains a uniquely coloured t-subset. For a wide class of “well-behaved” geometrically defined hypergraphs, we provide near tight upper bounds on their t-subset conflict-free chromatic number. For t=2 we show that for each of those “well-behaved” hypergraphs H, the hypergraph H′, whose hyperedges are obtained by taking all the unions of two hyperedges from H, admits a 2-subset conflict-free colouring with roughly the same number of colours as H. For example, we show that the n2 pairs of points in any set P of n points in the plane can be coloured with O(logn) colours such that for any two discs d1,d2 in the plane with |(d1∪d2)∩P|≥2 there is a uniquely (in d1∪d2) coloured pair. We also show that there is no general bound on the t-subset conflict-free chromatic number as a function of the standard conflict-free chromatic number already for t=2.

AB - We introduce and study conflict-free colourings of t-subsets in hypergraphs. In such colourings, one assigns colours to all subsets of vertices of cardinality t such that in any hyperedge of cardinality at least t there is a uniquely coloured t-subset. The case t=1, i.e., vertex conflict-free colouring, is a well-studied notion that originates in the context of frequency allocation to antennas in cellular networks. It has caught the attention of researchers both from the combinatorial and algorithmic points of view. A special focus was given to hypergraphs arising in geometry. Already the case t=2 (i.e., colouring pairs) seems to present a new challenge. Many of the tools used for conflict-free colouring of geometric hypergraphs rely on hereditary properties of the underlying hypergraphs. When dealing with subsets of vertices, the properties do not pass to subfamilies of subsets. Therefore, we develop new tools, which might be of independent interest. For any fixed t, we show that the ntt-subsets in any set P of n points in the plane can be coloured with O(t2log2n) colours so that any axis-parallel rectangle that contains at least t points of P also contains a uniquely coloured t-subset. For a wide class of “well-behaved” geometrically defined hypergraphs, we provide near tight upper bounds on their t-subset conflict-free chromatic number. For t=2 we show that for each of those “well-behaved” hypergraphs H, the hypergraph H′, whose hyperedges are obtained by taking all the unions of two hyperedges from H, admits a 2-subset conflict-free colouring with roughly the same number of colours as H. For example, we show that the n2 pairs of points in any set P of n points in the plane can be coloured with O(logn) colours such that for any two discs d1,d2 in the plane with |(d1∪d2)∩P|≥2 there is a uniquely (in d1∪d2) coloured pair. We also show that there is no general bound on the t-subset conflict-free chromatic number as a function of the standard conflict-free chromatic number already for t=2.

KW - 05C15

KW - 52C45

KW - Conflict-free

KW - Geometric hypergraphs

KW - Hypergraph colouring

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

U2 - 10.1007/s00454-023-00516-x

DO - 10.1007/s00454-023-00516-x

M3 - ???researchoutput.researchoutputtypes.contributiontojournal.article???

AN - SCOPUS:85165303615

SN - 0179-5376

VL - 72

SP - 876

EP - 891

JO - Discrete and Computational Geometry

JF - Discrete and Computational Geometry

IS - 2

ER -