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

Povzetek

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$▫.

Ključne besede

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

Podatki

Jezik:	Angleški jezik
Leto izida:	2011
Tipologija:	1.01 - Izvirni znanstveni članek
Organizacija:	UM FS - Fakulteta za strojništvo
UDK:	519.17
COBISS:	16079705
ISSN:	0195-6698
Št. ogledov:	34
Št. prenosov:	21
Ocena:	0 (0 glasov)
Metapodatki:

Ostali podatki

Sekundarni jezik:	Angleški jezik
Sekundarne ključne besede:	matematika;teorija grafov;neodvisnostno število;kartezični produkt grafov;
Vrsta dela (COBISS):	Delo ni kategorizirano
Strani:	str. 1377-1383
Letnik:	Vol. 32
Zvezek:	no. 8
Čas izdaje:	2011
ID:	1475892