Equitable colorings of Cartesian products of graphs

Wu-Hsiung Lin, Gerard J. Chang*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

15 Scopus citations

Abstract

The present paper studies the following variation of vertex coloring on graphs. A graph G is equitably k-colorable if there is a mapping fV(G)→1,2,⋯,k such that f(x)≠f(y) for xy∈E(G) and ||f- 1(i)|-|f-1(j)||≤1 for 1≤i,j≤k. The equitable chromatic number of a graph G, denoted by χ=(G), is the minimum k such that G is equitably k-colorable. The equitable chromatic threshold of a graph G, denoted by χ=*(G), is the minimum t such that G is equitably k-colorable for all k<t. Our focus is on the equitable colorability of Cartesian products of graphs. In particular, we give exact values or upper bounds of χ=(G□H) and χ=*(G□H) when G and H are cycles, paths, stars, or complete bipartite graphs.

Original languageEnglish
Pages (from-to)239-247
Number of pages9
JournalDiscrete Applied Mathematics
Volume160
Issue number3
DOIs
StatePublished - 1 Feb 2012

Keywords

  • Cartesian product
  • Equitable chromatic number
  • Equitable chromatic threshold
  • Equitable coloring

Fingerprint Dive into the research topics of 'Equitable colorings of Cartesian products of graphs'. Together they form a unique fingerprint.

Cite this