THE EQUITABLE CHROMATIC THRESHOLD OF THE CARTESIAN PRODUCT OF BIPARTITE GRAPHS IS AT MOST 4

Abstract

A graph G is equitably k-colorable if its vertex set can be partitioned into k independent sets, any two of which differ in size by at most 1. We prove a conjecture of Lin and Chang which asserts that for any bipartite graphs G and H, their Cartesian product G square H is equitably k-colorable whenever k >= 4.