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 GH is equitably k-colorable whenever k ≥ 4.
- Bipartite graph
- Cartesian product
- Equitable chromatic threshold
- Equitable coloring