A hyperedge coloring and application in combinatorial testing

Abstract

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 [Formula: see text] the r-uniform complete r-partite hypergraph [Formula: see text] 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.

Keywords

• Uniform coloring
• equitable coloring
• balanced hypergraph
• covering array on hypergraph