A hyperedge coloring and application in combinatorial testing
Yasmeen Akhtar · AKCE International Journal of Graphs and Combinatorics · 2022
For a hypergraph H, a uniform k-coloring of hyperedges always has the same (to within 1) number of hyperedges of each color, whereas an equitable k-coloring of hyperedges has the property that at every vertex all the colors incident the same number of times (to within 1). For every k≥2, the r-uniform complete r-partite hypergraph Kn1,n2,…,nrr always admits an equitable k-coloring of hyperedges that is also uniform. This paper establishes the existence of an equitable and uniform coloring of hyperedges in a 3-uniform complete tripartite (multi)hypergraph such that the hyperedges of the same color form a connected partial hypergraph with the property that subhypergraph induced by a pair of parts of its vertex set is a complete bipartite graph. Further, we use this coloring for introducing a new hyperedge-hooking operation to construct optimal size mixed covering arrays on hypergraphs.