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

Špacapan, Simon

| | SLO | ENG | Cookies and privacy

Bigger font | Smaller font

First page > Show document

Show document

Title:	The k-independence number of direct products of graphs and Hedetniemi's conjecture
Authors:	ID Špacapan, Simon (Author)
Files:	http://dx.doi.org/10.1016/j.ejc.2011.07.002
Language:	English
Work type:	Not categorized
Typology:	1.01 - Original Scientific Article
Organization:	FS - Faculty of Mechanical Engineering
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
Year of publishing:	2011
Number of pages:	str. 1377-1383
Numbering:	Vol. 32, no. 8
PID:	20.500.12556/DKUM-51910
UDC:	519.17
ISSN on article:	0195-6698
COBISS.SI-ID:	16079705
NUK URN:	URN:SI:UM:DK:NWLVHO8H
Publication date in DKUM:	10.07.2015
Views:	1487
Downloads:	68
Metadata:
Categories:	Misc.
:	ŠPACAPAN, Simon, 2011, The k-independence number of direct products of graphs and Hedetniemi’s conjecture. European journal of combinatorics [online]. 2011. Vol. 32, no. 8, p. 1377–1383. [Accessed 22 March 2025]. Retrieved from: http://dx.doi.org/10.1016/j.ejc.2011.07.002 Copy citation