About Colorings of (3,3)-Uniform Complete Circular Mixed Hypergraphs

Abstract

A mixed hypergraph is a triple $\mathcal{H}=(X,\mathcal{C},\mathcal{D})$, where $X$ is the vertex set and each of $\mathcal{C}$ and $\mathcal{D}$ is a family of subsets of $X$, the $\mathcal{C}$-edges and $\mathcal{D}$-edges, respectively. A proper $k$-coloring of $\mathcal{H}$ is a mapping such that each $\mathcal{C}$-edge has two vertices with a common color and each $\mathcal{D}$-edge has two vertices with distinct colors. A mixed hypergraph $\mathcal{H}$ is called circular if there exists a host cycle on the vertex set $X$ such that every edge ($\mathcal{C}$- or $\mathcal{D}$-) induces a connected subgraph of this cycle. We propose an algorithm to color the $(3,3)$-uniform, complete, circular, mixed hypergraphs for every value in its feasible set. In doing so, we show: $\chi (\mathcal{H})=2$ and $\overline{\chi }(\mathcal{H})=\frac{n}{2}$ when $n$ is even and $\overline{\chi }(\mathcal{H})=\frac{n-1}{2}$ when $n$ is odd.