Feasible sets for vertex colorings of P4-designs

Abstract

A P₄-design of order v is a system Σ= (X,B) where X has v vertices and B is a set of copies of P₄, called blocks, decomposing the complete graph K_v on X. A BP₄-design is a P₄-design Σ endowed with a coloring of the vertices of $\Sigma$ in such a way that in any block there are at least two vertices with the same color and two vertices with different colors. The feasible set Ω(Σ) of $\Sigma$ is the set of integers k for which Σ is k-colorable. The minimum and maximum of Ω(Σ) are, respectively, the lower and upper chromatic number of Σ. In this paper the study of BP₄-designs is initiated, giving a lower and upper bound for feasible sets of BP₄-designs and showing the existence, for any admissible integer v, of BP₄-designs of order v with the largest possible feasible set. Some results are obtained for small values of v.