A hypergraph is 2-intersecting if any two edges intersect in at least two vertices. Blais, Weinstein and Yoshida asked (as a first step to a more general problem) whether every 2-intersecting hypergraph has a vertex coloring with a constant number of colors so that each hyperedge has at least $\min(|e|,3)$ colors. We show that there is such a coloring with at most 5 colors (which is best possible).
@article{10_37236_3600,
author = {Lucas Colucci and Andr\'as Gy\'arf\'as},
title = {Coloring 2-intersecting hypergraphs},
journal = {The electronic journal of combinatorics},
year = {2013},
volume = {20},
number = {3},
doi = {10.37236/3600},
zbl = {1295.05102},
url = {http://geodesic.mathdoc.fr/articles/10.37236/3600/}
}
TY - JOUR
AU - Lucas Colucci
AU - András Gyárfás
TI - Coloring 2-intersecting hypergraphs
JO - The electronic journal of combinatorics
PY - 2013
VL - 20
IS - 3
UR - http://geodesic.mathdoc.fr/articles/10.37236/3600/
DO - 10.37236/3600
ID - 10_37236_3600
ER -
%0 Journal Article
%A Lucas Colucci
%A András Gyárfás
%T Coloring 2-intersecting hypergraphs
%J The electronic journal of combinatorics
%D 2013
%V 20
%N 3
%U http://geodesic.mathdoc.fr/articles/10.37236/3600/
%R 10.37236/3600
%F 10_37236_3600
Lucas Colucci; András Gyárfás. Coloring 2-intersecting hypergraphs. The electronic journal of combinatorics, Tome 20 (2013) no. 3. doi: 10.37236/3600
