# The $k$-independence number of direct products of graphs

###
Simon Špacapan

FME, UM

PDF

**Minisymposium:**
GRAPH PRODUCTS

**Content:**
The $k$-independence number of $G$, denoted as $\alpha_k(G)$, is the size of a largest $k$-colorable subgraph of $G$.
We conjecture that for any graphs $G$ and $H$,
$$\alpha_k(G\times H)\leq \alpha_k(G)|V(H)|+\alpha_k(H)|V(G)|-\alpha_k(G)\alpha_k(H)\,.$$
The conjecture is stronger than the Hedetniemi's conjecture, and it was proved for $k=1,2$. For $k=3$ the conjecture implies
the result of El-Zahar and Sauer that the direct product of 4-chromatic graphs is 4-chromatic. Under some additional conditions the conjecture is also true for $k=3$, and in this talk we discuss these conditions.