On the balanced upper chromatic number of finite projective planes

Blázsik, L. Zoltán and Blokhuis, Aart and Miklavic, Stefko and Nagy, Zoltán Lóránt and Szőnyi, Tamás (2021) On the balanced upper chromatic number of finite projective planes. DISCRETE MATHEMATICS, 344 (3). ISSN 0012-365X

Preview

Text Balanced_upper_chromatic_number_of_PG_2_q_revision.pdf Download (526kB) | Preview

Abstract

In this paper, we study vertex colorings of hypergraphs in which all color class sizes differ by at most one (balanced colorings) and each hyperedge contains at least two vertices of the same color (rainbow-free colorings). For any hypergraph H, the maximum number k for which there is a balanced rainbow-free k-coloring of H is called the balanced upper chromatic number of the hypergraph. We confirm the conjecture of Araujo-Pardo, Kiss and Montejano by determining the balanced upper chromatic number of the desarguesian projective plane PG(2,q) for all q. In addition, we determine asymptotically the balanced upper chromatic number of several families of non-desarguesian projective planes and also provide a general lower bound for arbitrary projective planes using probabilistic methods which determines the parameter up to a multiplicative constant.

Actions (login required)

Edit Item