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)|\le 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).