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.

Back to all abstracts