zbMATH — the first resource for mathematics

Graph homomorphisms via vector colorings. (English) Zbl 1414.05199
Summary: In this paper we study the existence of homomorphisms \(G \to H\) using semidefinite programming. Specifically, we use the vector chromatic number of a graph, defined as the smallest real number \(t \geq 2\) for which there exists an assignment of unit vectors \(i \mapsto p_i\) to its vertices such that \(\langle p_i, p_j \rangle \leq - 1 /(t - 1),\) when \(i \sim j\). Our approach allows to reprove, without using the Erdős-Ko-Rado theorem, that for \(n > 2 r\) the Kneser graph \(K_{n : r}\) and the \(q\)-Kneser graph \(q K_{n : r}\) are cores, and furthermore, that for \(n / r = n^\prime / r^\prime\) there exists a homomorphism \(K_{n : r} \to K_{n^\prime : r^\prime}\) if and only if \(n\) divides \(n^\prime\). In terms of new applications, we show that the even-weight component of the distance \(k\)-graph of the \(n\)-cube \(H_{n, k}\) is a core and also, that non-bipartite Taylor graphs are cores. Additionally, we give a necessary and sufficient condition for the existence of homomorphisms \(H_{n, k} \to H_{n^\prime, k^\prime}\) when \(n / k = n^\prime /k^\prime\). Lastly, we show that if a 2-walk-regular graph (which is non-bipartite and not complete multipartite) has a unique optimal vector coloring, it is a core. Based on this sufficient condition we conducted a computational study on Ted Spence’s list of strongly regular graphs [“Strongly regular graphs on at most 64 vertices”, http://www.maths.gla.ac.uk/~es/srgraphs.php] and found that at least 84% are cores.

05C60 Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)
05C15 Coloring of graphs and hypergraphs
90C22 Semidefinite programming
Full Text: DOI arXiv
[1] Babai, László, Spectra of Cayley graphs, J. Comb. Theory B, 27, 2, 180-189, (1979) · Zbl 0338.05110
[2] Brouwer, Andries E.; Cohen, Arjeh M.; Neumaier, Arnold, Distance-Regular Graphs, (1989), Springer · Zbl 0747.05073
[3] Cameron, Peter J.; Kazanidis, Priscila A., Cores of symmetric graphs, J. Aust. Math. Soc., 85, 145-154, (2008) · Zbl 1167.05032
[4] Chowdhury, Ameera; Godsil, Chris D.; Royle, Gordon F., Colouring lines in projective space, J. Combin. Theory Ser. A, 39-52, (2006) · Zbl 1082.05035
[5] Engström, Robert; Färnqvist, Tommy; Jonsson, Peter; Thapper, Johan, Thapper an approximability-related parameter on graphs - properties and applications, Discrete Math. Theor. Comput. Sci., 17, 1, (2015) · Zbl 1306.05058
[6] Godsil, Chris D., Problems in algebraic combinatorics, Electron. J. Combin., 2, (1995)
[7] Godsil, Christopher D.; Meagher, Karen, Erdös-Ko-Rado Theorems: Algebraic Approaches, Vol. 149, (2015), Cambridge University Press · Zbl 1343.05002
[8] Godsil, Chris D.; Roberson, David E.; Rooney, Brendan; Šámal, Robert; Varvitsiotis, A., Universal completability least eigenvalue frameworks and vector colorings,, Discrete Comput. Geom., 58, 2, 265-292, (2017) · Zbl 1371.05162
[9] Godsil, Chris D.; Roberson, David E.; Šámal, Robert; Severini, Simone, Sabidussi versus Hedetniemi for three variations of the chromatic number, Combinatorica, 1-21, (2015) · Zbl 1389.05040
[10] Godsil, Chris D.; Royle, Gordon F., Algebraic Graph Theory, Vol. 207, (2001), Springer GTM · Zbl 0968.05002
[11] Hahn, Geňa; Tardif, Claude, Graph Homomorphisms: Structure and Symmetry, 107-166, (1997), Springer Netherlands: Springer Netherlands Dordrecht · Zbl 0880.05079
[12] Hell, Pavol; Nešetřil, Jaroslav, On the complexity of H-colourings, J. Combin. Theory Ser. B, 48, 92-110, (1990) · Zbl 0639.05023
[13] Hell, Pavol; Nešetřil, Jaroslav, The core of a graph, Discrete Math., 109, 1, 117-126, (1992) · Zbl 0803.68080
[14] Hell, Pavol; Nešetřil, Jaroslav, Graphs and Homomorphisms, (2004), Oxford Univerity Press · Zbl 1062.05139
[15] Karger, David; Motwani, Rajeev; Sudan, Madhu, Approximate graph coloring by semidefinite programming, J. ACM, 45, 2, 246-265, (1998) · Zbl 0904.68116
[16] Keller-Gehrig, Walter, Fast algorithms for the characteristics polynomial, Theoret. Comput. Sci., 36, 309-317, (1985) · Zbl 0565.68041
[17] Laurent, Monique; Varvitsiotis, Antonios, Positive semidefinite matrix completion, universal rigidity and the strong Arnold property, Linear Algebra Appl., 452, 292-317, (2014) · Zbl 1291.90165
[18] Lovász, László, Spectra of graphs with transitive groups, Period. Math. Hungar., 6, 2, 191-195, (1975) · Zbl 0395.05057
[19] McEliece, Robert J.; Rodemich, Eugene R.; Rumsey, H. C., The Lovász bound and some generalizations, J. Comb. Inf. Syst. Sci., 3, 134-152, (1978) · Zbl 0408.05031
[20] Nešetřil, Jaroslav, Homomorphisms of derivative graphs, Discrete Math., 1, 3, 257-268, (1971) · Zbl 0227.05109
[21] Pak, Igor; Vilenchik, Dan, Constructing uniquely realizable graphs, Discrete Comput. Geom., 50, 4, 1051-1071, (2013) · Zbl 1280.05092
[22] Roberson, David E., Homomorphisms of Strongly Regular Graphs, (2016), arXiv:1601.00969 · Zbl 1356.05156
[23] Schrijver, Alexander, A comparison of the Delsarte and Lovász bounds, IEEE Trans. Inform. Theory, 25, 4, 425-429, (1979) · Zbl 0444.94009
[24] Stahl, Saul, \(n\)-Tuple colorings and associated graphs, J. Combin. Theory Ser. B, 20, 2, 185-203, (1976) · Zbl 0293.05115
[25] Ted Spence’s webpage: Strongly regular graphs on at most 64 vertices. http://www.maths.gla.ac.uk/ es/srgraphs.php.
[26] The Sage Developers. Sage Mathematics Software (Version 6.9), http://www.sagemath.org 2015.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.