Coloring hypergraphs defined by stabbed pseudo-disks and ABAB-free hypergraphs
Acta mathematica Universitatis Comenianae, Tome 88 (2019) no. 3, pp. 363-370
Eyal Ackerman; Balazs Keszegh; Dömötör Pálvölgyi; Eyal Ackerman; Balazs Keszegh; Dömötör Pálvölgyi. Coloring hypergraphs defined by stabbed pseudo-disks and ABAB-free hypergraphs. Acta mathematica Universitatis Comenianae, Tome 88 (2019) no. 3, pp. 363-370. http://geodesic.mathdoc.fr/item/AMUC_2019_88_3_a1/
@article{AMUC_2019_88_3_a1,
     author = {Eyal Ackerman and Balazs Keszegh and D\"om\"ot\"or P\'alv\"olgyi and Eyal Ackerman and Balazs Keszegh and D\"om\"ot\"or P\'alv\"olgyi},
     title = { Coloring hypergraphs defined by stabbed pseudo-disks and {ABAB-free} hypergraphs},
     journal = {Acta mathematica Universitatis Comenianae},
     pages = {363--370},
     year = {2019},
     volume = {88},
     number = {3},
     url = {http://geodesic.mathdoc.fr/item/AMUC_2019_88_3_a1/}
}
TY  - JOUR
AU  - Eyal Ackerman
AU  - Balazs Keszegh
AU  - Dömötör Pálvölgyi
AU  - Eyal Ackerman
AU  - Balazs Keszegh
AU  - Dömötör Pálvölgyi
TI  - Coloring hypergraphs defined by stabbed pseudo-disks and ABAB-free hypergraphs
JO  - Acta mathematica Universitatis Comenianae
PY  - 2019
SP  - 363
EP  - 370
VL  - 88
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/AMUC_2019_88_3_a1/
ID  - AMUC_2019_88_3_a1
ER  - 
%0 Journal Article
%A Eyal Ackerman
%A Balazs Keszegh
%A Dömötör Pálvölgyi
%A Eyal Ackerman
%A Balazs Keszegh
%A Dömötör Pálvölgyi
%T Coloring hypergraphs defined by stabbed pseudo-disks and ABAB-free hypergraphs
%J Acta mathematica Universitatis Comenianae
%D 2019
%P 363-370
%V 88
%N 3
%U http://geodesic.mathdoc.fr/item/AMUC_2019_88_3_a1/
%F AMUC_2019_88_3_a1

Voir la notice de l'article provenant de la source Comenius University

What is the minimum number of colors that always suffice to color every planar set of points such that any disk that contains enough points contains two points of different colors? It is known that the answer to this question is either three or four.We show that three colors always suffice if the condition must be satisfied only by disks that contain a fixed point.Our result also holds, and is even tight, when instead of disks we consider their topological generalization, namely \emph{pseudo-disks}, with a non-empty intersection.Our solution uses the equivalence that a hypergraph can be realized by stabbed pseudo-disks if and only ifit is \emph{$ABAB$-free}.These hypergraphs are defined in a purely abstract, combinatorial way and our proof that they are $3$-chromatic is also combinatorial.