Vertex-Equalized Edge-Colorings

Abstract

We define a new fairness notion on edge-colorings, requiring that the number of vertices in the subgraphs induced by the edges of each color are within one of each other. Given a (not necessarily proper) \( k \)-edge-coloring of a graph \( G \), for each color \( i \in \mathbb{Z}_k \), let \( G[i] \) denote the (not necessarily spanning) subgraph of \( G \) induced by the edges colored \( i \). Let \( \nu_{i}(G) = |V(G[i])| \). Formally, a \( k \)-edge-coloring of a graph \( G \) is said to be vertex-equalized if for each pair of colors \( i, j \in \mathbb{Z}_k \), \( |\nu_{i}(G) – \nu_{j}(G)| \leq 1 \). In this paper, a characterization is found for connected graphs that have vertex-equalized \( k \)-edge-colorings for each \( k \in \{2, 3\} \) (see Corollary 4.1 and Corollary 4.2).