On Evenly-Equitable, Balanced Edge-Colorings and Related Notions. (5th April 2015)

• Record Type: Journal Article
• Authors: Erzurumluoğlu, Aras; Rodger, C. A.
• Other Names: Mansour Toufik Academic Editor.
• Is Part Of: International journal of combinatorics. Volume 2015(2015)
• Publication Date: 2015-04-05
• Subjects: Combinatorial analysis -- Periodicals; Combinatorial analysis; Periodicals; Electronic journals; 511.605
• DOI: 10.1155/2015/201427
• Languages: English
• ISSNs: 1687-9163

Abstract

Abstract : 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 ∈ Z k = { 0, 1, …, 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 ∈ 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 ∈ Z k, G ( i ) is an even graph, and for each vertex v ∈ V ( G ) and for any pair of colors i, j ∈ Z k, | deg G ( i ) ( v ) - deg G ( j ) ( v ) | ∈ { 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 } ) | ≤ 1 . Hilton proved that each even graph has an evenly-equitable k -edge-coloring for each k ∈ 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 ∈ 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.