On 3-Colorings of Direct Products of Graphs

摘要

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 α k ( G × H ) ≤ α k ( G ) | V ( H ) | + α k ( H ) | V ( G ) | ? α k ( G ) α k ( H ) , and proved the conjecture for k = 1 and k = 2. If true for k = 3 the conjecture strenghtens the result of El-Zahar and Sauer who proved that any direct product of 4-chromatic graphs is 4-chromatic [M. El-Zahar and N. Sauer, The chromatic number of the product of two 4 -chromatic graphs is 4, Combinatorica 5 (1985) 121–126]. In this paper we prove that the above bound is true for k = 3 provided that G and H are graphs that have complete tripartite subgraphs of orders α _(3)( G ) and α _(3)( H ), respectively.