On evenly-equitable, balanced edge-colorings and related notions
type: Item
instance of: scholarly article
title: On evenly-equitable, balanced edge-colorings and related notions
zbMATH Open document ID: 1322.05057
DOI: 10.1155/2015/201427
author: Aras Erzurumluoğlu
author: C. A. Rodger
published in: International Journal of Combinatorics
publication date: 2015-10-06T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05C15
zbMATH DE Number: 6489887
zbMATH Keywords: even \(k\)-edge-coloring
zbMATH Keywords: even graph
Wikidata QID: Q59106871
MaRDI profile type: Publication
full work available at URL: https://doi.org/10.1155/2015/201427
OpenAlex ID: W2067021421
cites work: Q5627909
cites work: Q5650698
cites work: Q4053562
cites work: On A Particular Conference Scheduling Problem
cites work: Canonical edge-colourings of locally finite graphs
cites work: Class one graphs
cites work: The chromatic index of complete multipartite graphs
cites work: A sufficient condition for equitable edge-colourings of simple graphs
cites work: Equitable edge-colorings of simple graphs
cites work: \((r,r+1)\)-factorizations of \((d,d+1)\)-graphs
cites work: Fair Hamilton decompositions of complete multipartite graphs
cites work: Fair 1-factorizations and fair holey 1-factorizations of complete multipartite graphs
cites work: Multiply balanced edge colorings of multigraphs
cites work: Q3097395
description: scientific article; zbMATH DE number 6489887