Homogeneous edge-colorings of graphs
type: Item
instance of: scholarly article
zbMATH Open document ID: 1358.05094
author: Paola Bonacini
author: Maria Grazia Cinquegrani
author: Lucia Marino
publication date: 2016-11-10T00:00:00Z
full work available at URL: https://arxiv.org/abs/1203.4531
Mathematics Subject Classification ID: 05C15
zbMATH DE Number: 6651228
zbMATH Keywords: edge coloring
zbMATH Keywords: homogeneous edge coloring
MaRDI profile type: Publication
arXiv ID: 1203.4531
arXiv classification: math.CO
title: Homogeneous edge-colorings of graphs
published in: Utilitas Mathematica
review text: Let \(G = (V, E)\) be a multigraph without loops. For any \(x \in V\), let \(E(x)\) be the set of edges of \(G\) incident to \(x\). A homogeneous edge-coloring of \(G\) is an assignment of an integer \(m \geq 2\) and a coloring \(c : E \rightarrow S\) of the edges of \(G\) such that \(|S| = m\) and for any \(x \in V\), if \(|E(x)| = m q_x + r_x\) with \(0 \leq r_x < m\), there exists a partition of \(E(x)\) in \(r_x\) color classes of cardinality \(q_x + 1\) and other \( m - r_x\) color classes of cardinality \(q_x\). The homogeneous chromatic index \({\chi}_h(G)\) is the least \(m\) for which there exists such a coloring. In this paper, the authors determined \({\chi}_h(G)\) when \(G\) is a complete multigraph, a tree, or a complete bipartite multigraph.
reviewed by: Rao Li
description: scientific article; zbMATH DE number 6651228