Coloring Properties of Mixed Cycloids

Abstract

In this paper, we investigate partitions of highly symmetrical discrete structures called cycloids. In general, a mixed hypergraph has two types of hyperedges. The vertices are colored in such a way that each C-edge has two vertices of the same color, and each D-edge has two vertices of distinct colors. In our case, a mixed cycloid is a mixed hypergraph whose vertices can be arranged in a cyclic order, and every consecutive p vertices form a C-edge, and every consecutive q vertices form a D-edge in the ordering. We completely determine the maximum number of colors that can be used for any p≥3 and any q≥2. We also develop an algorithm that generates a coloring with any number of colors between the minimum and maximum. Finally, we discuss the colorings of mixed cycloids when the maximum number of colors coincides with its upper bound, which is the largest cardinality of a set of vertices containing no C-edge.

Keywords

• coloring
• circular hypergraph
• mixed hypergraph