On 3-Colorings of Direct Products of Graphs

Abstract

The k-independence number of a graph G, denoted as αk(G), is the order of a largest induced k-colorable subgraph of G. In [S. Špacapan, The k-independence number of direct products of graphs, European J. Combin. 32 (2011) 1377–1383] the author conjectured that the direct product G × H of graphs G and H obeys the following bound

Keywords

• independence number
• direct product
• hedetniemi’s conjecture
• 05c15
• 05c69
• 05c67