Altermatic number of categorical product of graphs

Meysam Alishahi, Hossein Hajiabolhassan*

*Corresponding author for this work

Research output: Contribution to journalJournal articleResearchpeer-review

Abstract

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
Volume341
Issue number5
Pages (from-to)1316-1324
ISSN0012-365X
DOIs
Publication statusPublished - 2018

Keywords

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

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

Cite this