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 |