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/

[1] N. Alon, I. Dinur, E. Friedgut and B. Sudakov, Graph products, Fourier analysis and spectral techniques, Geom. Funct. Anal. 14 (2004) 913–940. doi:10.1007/s00039-004-0478-3

[2] M. El-Zahar and N. Sauer, The chromatic number of the product of two 4 -chromatic graphs is 4, Combinatorica 5 (1985) 121–126. doi:10.1007/BF02579374

[3] D. Greenwell and L. Lovász, Applications of product colouring, Acta Math. Acad. Sci. Hungar. 25 (1974) 335–340. doi:10.1007/BF01886093

[4] X.B. Geng, J. Wang and H. Zhang, Structure of independent sets in direct products of some vertex-transitive graphs, Acta Math. Sin. (Engl. Ser.) 28 (2012) 697–706. doi:10.1007/s10114-011-0311-5

[5] R. Hammack, W. Imrich and S. Klavžar, Handbook of Product Graphs, Second Edition (CRC Press, Boca Raton, FL, 2011).

[6] S.T. Hedetniemi, Homomorphisms and graph automata, University of Michigan Technical Report 03105–44–T (1966).

[7] P.K. Jha and S. Klavžar, Independence in direct-product graphs, Ars Combin. 50 (1998) 53–63.

[8] B. Larose and C. Tardif, Projectivity and independent sets in powers of graphs, J. Graph Theory 40 (2002) 162–171. doi:10.1002/jgt.10041

[9] S. Špacapan, The k-independence number of direct products of graphs and Hedetniemi’s conjecture, European J. Combin 32 (2011) 1377–1383. doi:10.1016/j.ejc.2011.07.002

[10] C. Tardif, Hedetniemi’s conjecture 40 years later, Graph Theory Notes of New York LIV (2008) 46–57.

[11] C. Tardif, Hedetniemi’s conjecture and dense Boolean lattices, Order 28 (2011) 181–191. doi:10.1007/s11083-010-9162-4

[12] Á. Tóth, On the ultimate categorical independence ratio, J. Combin. Theory Ser. B 108 (2014) 29–39. doi:10.1016/j.jctb.2014.02.010

[13] M. Valencia-Pabon and J. Vera, Independence and coloring properties of direct products of some vertex-transitive graphs, Discrete Math. 306 (2006) 2275–2281. doi:10.1016/j.disc.2006.04.013

[14] H. Zhang, Primitivity and independent sets in direct products of vertex-transitive graphs, J. Graph Theory 67 (2011) 218–225. doi:10.1002/jgt.20526

[15] H. Zhang, Independent sets in direct products of vertex-transitive graphs, J. Combin. Theory Ser. B 102 (2012) 832–838. doi:10.1016/j.jctb.2011.12.005

[16] X. Zhu, A survey on Hedetniemi’s conjecture, Taiwanese J. Math. 2 (1998) 1–24. doi:10.11650/twjm/1500406890

[17] X. Zhu, The fractional version of Hedetniemi’s conjecture is true, European J. Com-bin. 32 (2011) 1168–1175. doi:10.1016/j.ejc.2011.03.004