Geodesic
On 3-Colorings of Direct Products of Graphs
Discussiones Mathematicae. Graph Theory, Tome 39 (2019) no. 2, pp. 391-413

Voir la notice de l'article provenant de la source Library of Science

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.
Keywords: independence number, direct product, Hedetniemi’s conjecture 
@article{DMGT_2019_39_2_a7,
     author = {\v{S}pacapan, Simon},
     title = {On {3-Colorings} of {Direct} {Products} of {Graphs}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {391--413},
     publisher = {mathdoc},
     volume = {39},
     number = {2},
     year = {2019},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2019_39_2_a7/}
}
TY  - JOUR
AU  - Špacapan, Simon
TI  - On 3-Colorings of Direct Products of Graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2019
SP  - 391
EP  - 413
VL  - 39
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2019_39_2_a7/
LA  - en
ID  - DMGT_2019_39_2_a7
ER  - 
%0 Journal Article
%A Špacapan, Simon
%T On 3-Colorings of Direct Products of Graphs
%J Discussiones Mathematicae. Graph Theory
%D 2019
%P 391-413
%V 39
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2019_39_2_a7/
%G en
%F DMGT_2019_39_2_a7
Špacapan, Simon. On 3-Colorings of Direct Products of Graphs. Discussiones Mathematicae. Graph Theory, Tome 39 (2019) no. 2, pp. 391-413. http://geodesic.mathdoc.fr/item/DMGT_2019_39_2_a7/