The k-independence number of direct products of graphs and Hedetniemi's conjecture

Abstract

The ▫$k$▫-independence number of ▫$G$▫, denoted as ▫$\alpha_k(G)$▫, is the size of a largest ▫$k$▫-colorable subgraph of ▫$G$▫. The direct product of graphs ▫$G$▫ and ▫$H$▫, denoted as ▫$G \times H$▫, is the graph with vertex set ▫$V(G) \times V(H)$▫, where two vertices ▫$(x_1, y_1)$▫ and ▫$(x_2, y_2)$▫ are adjacent in ▫$G \times H$▫, if ▫$x_1$▫ is adjacent to ▫$x_2$▫ in ▫$G$▫ and ▫$y_1$▫ is adjacent to ▫$y_2$▫ in ▫$H$▫. We conjecture that for any graphs ▫$G$▫ and ▫$H$▫, ▫$$\alpha_k(G \times H) \ge \alpha_k(G)|V(H)| + \alpha_k(H)|V(G)| - \alpha_k(G) \alpha_k(H).$$▫ The conjecture is stronger than Hedetniemi's conjecture. We prove the conjecture for ▫$k = 1, 2$▫ and prove that ▫$\alpha_k(G \times H) \ge \alpha_k(G)|V(H)| + \alpha_k(H)|V(G)| - \alpha_k(G) \alpha_k(H)$▫ holds for any ▫$k$▫.

Keywords

matematika;teorija grafov;neodvisnostno število;kartezični produkt grafov;mathematics;graph theory;independence number;Cartesian product of graphs;

Data

Language:	English
Year of publishing:	2011
Typology:	1.01 - Original Scientific Article
Organization:	UM FS - Faculty of Mechanical Engineering
UDC:	519.17
COBISS:	16079705
ISSN:	0195-6698
Views:	34
Downloads:	21
Average score:	0 (0 votes)
Metadata:

Other data

Secondary language:	English
Secondary keywords:	matematika;teorija grafov;neodvisnostno število;kartezični produkt grafov;
Type (COBISS):	Not categorized
Pages:	str. 1377-1383
Volume:	Vol. 32
Issue:	no. 8
Chronology:	2011
ID:	1475892