Altermatic number of categorical product of graphs

Meysam Alishahi, Hossein Hajiabolhassan*

*Corresponding author for this work

Research output: Contribution to journalJournal articleResearchpeer-review


In this paper, we prove some relaxations of Hedetniemi's conjecture in terms of altermatic number and strong altermatic number of graphs, two combinatorial parameters introduced by the present authors Alishahi and Hajiabolhassan (2015) providing two sharp lower bounds for the chromatic number of graphs. In terms of these parameters, we also introduce some sharp lower bounds for the chromatic number of the categorical product of two graphs. Using these lower bounds, we present some new families of graphs supporting Hedetniemi's conjecture.
Original languageEnglish
JournalDiscrete Mathematics
Issue number5
Pages (from-to)1316-1324
Publication statusPublished - 2018


  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics
  • Altermatic number
  • Chromatic number
  • Hedetniemi's conjecture
  • Strong altermatic number


Dive into the research topics of 'Altermatic number of categorical product of graphs'. Together they form a unique fingerprint.

Cite this