Homogeneous edge-colorings of graphs

MaRDI QIDQ2831592zbMATH OpenFDO

Authors Paola Bonacini, Maria Grazia Cinquegrani, Lucia Marino

Publication date 10 November 2016

Published in Utilitas Mathematica (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1203.4531

zbMATH Keywords

edge coloringhomogeneous edge coloring

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Abstract: Let G = (V, E) be a multigraph without loops and 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 >= 2 and a coloring c:E { o} S of the edges of Gsuchthat|S| = mandforanyx{in}V,if|E(x)| = mqx+rx with0 <= rx <m, there exists a partition of E(x) in rx color classes of cardinality qx + 1 and other m-rx color classes of cardinality qx. The homogeneous chromatic index c{hi}(G) is the least m for which there exists such a coloring. We determine c{hi}(G) in the case that G is a complete multigraph, a tree or a complete bipartite multigraph.

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.

Recommendations

• Equipartite edge colouring of multigraphs
• On equitable edge-coloring of multigraphs
• On the (p,q)-coloring of incidentors of an undirected multigraph
• A generalization of edge-coloring in graphs
• An edge colouring of multigraphs

Cited in

(7)

• Edge-switching homomorphisms of edge-coloured graphs
• A linear heterochromatic number of graphs
• Homomorphism-homogeneous \(L\)-colored graphs
• Equipartite edge colouring of multigraphs
• Edge homogeneous colorings
• From NMNR-coloring of hypergraphs to homogenous coloring of graphs
• Homogeneous colourings of graphs

This page was built for publication: Homogeneous edge-colorings of graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2831592)