Existence of Equitable \(h\)-Edge-Colorings of Type \(s = 2, 3 \) of \(K_t\)

A. Ikhani1, D. Kiani1,2
1Faculty of Mathematics and Computer Science, Amirkabir University of Technology, P.O. Box 15875-4413, Tehran, Iran
2School of Mathematics, Institute for Research in Fundamental Sciences (IPM), P.O. Box 19395-5746, Tehran, Iran

Abstract

An \(h\)-edge-coloring (block-coloring) of type \(s\) of a graph \(G\) is an assignment of \(h\) colors to the edges (blocks) of \(G\) such that for every vertex \(x\) of \(G\), the edges (blocks) incident with \(x\) are colored with \(s\) colors. For every color \(i\), \(\xi_{x,i}\) (\(\mathcal{B}_{x,i}\)) denotes the set of all edges (blocks) incident with \(x\) and colored by \(i\). An \(h\)-edge-coloring (\(h\)-block-coloring) of type \(s\) is equitable if for every vertex \(x\) and for colors \(i\), \(j\), \(||\xi_{x,i}| – |\xi_{x,j}|| \leq 1\) (\(||\mathcal{B}_{x,i}| – |\mathcal{B}_{x,j}|| \leq 1\)). In this paper, we study the existence of \(h\)-edge-colorings of type \(s = 2,3\) of \(K_t\) and then show that the solution of this problem induces the solution of the existence of a \(C_4\)-\(_tK_2\)-design having an equitable \(h\)-block-coloring of type \(s = 2,3\).