The equitable chromatic threshold of the Cartesian product of bipartite graphs is at most 4

Zhidan Yan, Wu-Hsiung Lin*, Wei Wang

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

2 Scopus citations

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 languageEnglish
Pages (from-to)773-780
Number of pages8
JournalTaiwanese Journal of Mathematics
Volume18
Issue number3
DOIs
StatePublished - 1 Jan 2014

Keywords

  • Bipartite graph
  • Cartesian product
  • Equitable chromatic threshold
  • Equitable coloring

Fingerprint Dive into the research topics of 'The equitable chromatic threshold of the Cartesian product of bipartite graphs is at most 4'. Together they form a unique fingerprint.

Cite this