On evenly-equitable, balanced edge-colorings and related notions (Q499817)

Summary: A graph \(G\) is said to be even if all vertices of \(G\) have even degree. Given a \(k\)-edge-coloring of a graph \(G\), for each color \(i\in \mathbb Z_k=\{0,1,\dots,k-1\}\) let \(G(i)\) denote the spanning subgraph of \(G\) in which the edge-set contains precisely the edges colored \(i\). A \(k\)-edge-coloring of \(G\) is said to be an even \(k\)-edge-coloring if for each color \(i\in \mathbb Z_k\), \(G(i)\) is an even graph. A \(k\)-edge-coloring of \(G\) is said to be evenly-equitable if for each color \(i\in \mathbb Z_k\), \(G(i)\) is an even graph, and for each vertex \(v\in V(G)\) and for any pair of colors \(i,j\in \mathbb Z_k\), \(|\deg G(i)(v)-\deg G(j)(v)|\in{0,2}\). For any pair of vertices \(\{v,w\}\) let \(m_G(\{v,w\})\) be the number of edges between \(v\) and \(w\) in \(G\) (we allow \(v=w\), where \(\{v,v\}\) denotes a loop incident with \(v\)). A \(k\)-edge-coloring of \(G\) is said to be balanced if for all pairs of colors \(i\) and \(j\) and all pairs of vertices \(v\) and \(w\) (possibly \(v=w\)), \(|m_G(i)(\{v,w\})-m_G(j)({v,w})|\leq 1\). \textit{A. J. Hilton} [Combinatorica 2, 37--51 (1982; Zbl 0494.05021)] proved that each even graph has an evenly-equitable \(k\)-edge-coloring for each \(k\in N\). In this paper we extend this result by finding a characterization for graphs that have an evenly-equitable, balanced \(k\)-edge-coloring for each \(k\in N\). Correspondingly we find a characterization for even graphs to have an evenly-equitable, balanced 2-edge-coloring. Then we give an instance of how evenly-equitable, balanced edge-colorings can be used to determine if a certain fairness property of factorizations of some regular graphs is satisfied. Finally we indicate how different fairness notions on edge-colorings interact with each other.