Journal article
Altermatic number of categorical product of graphs
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.
Language: | English |
---|---|
Year: | 2018 |
Pages: | 1316-1324 |
ISSN: | 1872681x and 0012365x |
Types: | Journal article |
DOI: | 10.1016/j.disc.2018.02.007 |
ORCIDs: | 0000-0001-6588-8520 |
Altermatic number Chromatic number Discrete Mathematics and Combinatorics Hedetniemi's conjecture Strong altermatic number Theoretical Computer Science