Equitable colorings of some cycle-based middle graphs

Dalibor Froncek1
1University of Minnesota Duluth

Abstract

An equitable vertex \(k\)-coloring of a graph \(G\) is a proper vertex coloring with \(k\) colors such that the size of any two color classes differ by at most one. It was conjectured by Meyer in 1973 that every graph other than the complete graph \(K_n\) or an odd cycle \(C_{2m+1}\) admits an equitable vertex coloring with at most \(\Delta(G)\) colors, where \(\Delta(G)\) is the maximum degree of a vertex in graph \(G\). We show that the conjecture is true for middle graphs of some cycle-based graphs.

Keywords: vertex coloring, equitable vertex coloring, middle graph