Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
8903009 | Discrete Mathematics | 2018 | 9 Pages |
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.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Meysam Alishahi, Hossein Hajiabolhassan,