A sufficient condition for equitable edge-colourings of simple graphs
type: Item
instance of: scholarly article
title: A sufficient condition for equitable edge-colourings of simple graphs
zbMATH Open document ID: 0798.05022
DOI: 10.1016/0012-365X(94)90112-0
published in: Discrete Mathematics
publication date: 1994-06-09T00:00:00Z
review text: For a finite, simple graph \(G\), let \(\varphi\) be an edge-colouring (not necessarily proper) of \(G\) with \(k\) colours \(c_ 1,c_ 2,\dots,c_ k\), and let \(c_ i(v)\) denote the set of edges incident with vertex \(v\) coloured with colour \(c_ i\). The edge-colouring \(\varphi\) is said to be equitable if, for each vertex \(v\) of \(G\), \[ \bigl|| c_ i(v)|- | c_ j(v)|\bigr|\leq 1\quad\text{for all } 1\leq i< j\leq k. \] The authors prove, among other results, that if \(k\geq 2\) and \(k\) does not divide \(d(v)\) for all vertices \(v\) of \(G\), then \(G\) has an equitable edge-colouring with \(k\) colours.
Mathematics Subject Classification ID: 05C15
zbMATH DE Number: 562591
zbMATH Keywords: simple graph
zbMATH Keywords: edge-colouring
zbMATH Keywords: equitable
author: A. J. W. Hilton
author: Dominique De Werra
reviewed by: H. P. Yap
MaRDI profile type: Publication
cites work: On edge-colorings of graphs.
cites work: Lower bounds on the cover-index of a graph
cites work: Q3941433
cites work: Q3214964
cites work: Equitable and proportional coloring of trees
cites work: Q5181716
cites work: Méthode et théorème général de coloration des aretes d'un multigraphe
cites work: On decompositions of a multi-graph into spanning subgraphs
cites work: Q5620621
cites work: A generalization of edge-coloring in graphs
cites work: Q3048855
cites work: Colouring the Edges of a Multigraph so that Each Vertex has at Most j , or at Least j , Edges of Each Colour on it
cites work: Class one graphs
cites work: Equitable Coloring
cites work: Q5650698
cites work: Obstructions for regular colorings
full work available at URL: 0012-365x(94)90112-0
OpenAlex ID: W1998963995
description: scientific article; zbMATH DE number 562591