Coloring Properties of Mixed Cycloids

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 col...

Full description

Saved in:
Bibliographic Details
Published in:Symmetry (Basel) 2021-08, Vol.13 (8), p.1539
Main Authors: Dósa, György, Newman, Nicholas, Tuza, Zsolt, Voloshin, Vitaly
Format: Article
Language:English
Subjects:
Algorithms
Apexes
circular hypergraph
Color
coloring
Cycloids
Graph coloring
Graph theory
Graphs
mixed hypergraph
Upper bounds
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:2073-8994
2073-8994
DOI:10.3390/sym13081539