B-chromatic numbers of powers of paths and cycles

Wu-Hsiung Lin*, Gerard J. Chang

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

2 Scopus citations

Abstract

The b-chromatic number χb(G) of a graph G is the maximum number k for which there is a mapping f:V(G)→{1,2,.,k} such that f(x)≠f(y) for each edge xy and for each 1≤i≤k there is a vertex xi with f(xi)=i adjacent to some yij with f(yij)=j for each j≠i. Effantin and Kheddouci (2003) [8] gave the exact values for χb(Pnp) and χb(Cnp), except for the case 2p+3≤n≤3p they only proved that χb(Cnp)≥min{n- p-1,⌊n+2p+23⌋}. They then conjectured that this lower bound is in fact the exact value. In this paper, we confirm the conjecture for ⌊9p+104⌋≤n≤3p and disprove the conjecture for 2p+3≤n≤⌊9p+64⌋.

Original languageEnglish
Pages (from-to)2532-2536
Number of pages5
JournalDiscrete Applied Mathematics
Volume161
Issue number16-17
DOIs
StatePublished - 1 Nov 2013

Keywords

  • Cycle
  • Path
  • Power
  • b-chromatic number b-coloring

Fingerprint Dive into the research topics of 'B-chromatic numbers of powers of paths and cycles'. Together they form a unique fingerprint.

Cite this