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 GH is equitably k-colorable whenever k ≥ 4.
Original language | English |
---|---|
Pages (from-to) | 773-780 |
Number of pages | 8 |
Journal | Taiwanese Journal of Mathematics |
Volume | 18 |
Issue number | 3 |
DOIs | |
State | Published - 1 Jan 2014 |
Keywords
- Bipartite graph
- Cartesian product
- Equitable chromatic threshold
- Equitable coloring