A sufficient condition for equitable edge-colourings of simple graphs (Q1322183): Difference between revisions

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.