Altermatic number of categorical product of graphs |
| |
| Authors: | Meysam Alishahi Hossein Hajiabolhassan |
| |
| Institution: | 1. Faculty of Mathematical Sciences, Shahrood University of Technology, Shahrood, Iran;2. Department of Applied Mathematics and Computer Science, Technical University of Denmark, DK-2800 Lyngby, Denmark;3. School of Computer Science, Institute for Research in Fundamental Sciences, Tehran, Iran |
| |
| 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: | Chromatic number Hedetniemi’s conjecture Altermatic number Strong altermatic number |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
