# 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.

##### MSC:
 05C60 Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) 05C15 Coloring of graphs and hypergraphs 90C22 Semidefinite programming
##### Keywords:
Kneser graph; Taylor graphs
SageMath
Full Text:
##### References:
  Babai, László, Spectra of Cayley graphs, J. Comb. Theory B, 27, 2, 180-189, (1979) · Zbl 0338.05110  Brouwer, Andries E.; Cohen, Arjeh M.; Neumaier, Arnold, Distance-Regular Graphs, (1989), Springer · Zbl 0747.05073  Cameron, Peter J.; Kazanidis, Priscila A., Cores of symmetric graphs, J. Aust. Math. Soc., 85, 145-154, (2008) · Zbl 1167.05032  Chowdhury, Ameera; Godsil, Chris D.; Royle, Gordon F., Colouring lines in projective space, J. Combin. Theory Ser. A, 39-52, (2006) · Zbl 1082.05035  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  Godsil, Chris D., Problems in algebraic combinatorics, Electron. J. Combin., 2, (1995)  Godsil, Christopher D.; Meagher, Karen, Erdös-Ko-Rado Theorems: Algebraic Approaches, Vol. 149, (2015), Cambridge University Press · Zbl 1343.05002  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  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  Godsil, Chris D.; Royle, Gordon F., Algebraic Graph Theory, Vol. 207, (2001), Springer GTM · Zbl 0968.05002  Hahn, Geňa; Tardif, Claude, Graph Homomorphisms: Structure and Symmetry, 107-166, (1997), Springer Netherlands: Springer Netherlands Dordrecht · Zbl 0880.05079  Hell, Pavol; Nešetřil, Jaroslav, On the complexity of H-colourings, J. Combin. Theory Ser. B, 48, 92-110, (1990) · Zbl 0639.05023  Hell, Pavol; Nešetřil, Jaroslav, The core of a graph, Discrete Math., 109, 1, 117-126, (1992) · Zbl 0803.68080  Hell, Pavol; Nešetřil, Jaroslav, Graphs and Homomorphisms, (2004), Oxford Univerity Press · Zbl 1062.05139  Karger, David; Motwani, Rajeev; Sudan, Madhu, Approximate graph coloring by semidefinite programming, J. ACM, 45, 2, 246-265, (1998) · Zbl 0904.68116  Keller-Gehrig, Walter, Fast algorithms for the characteristics polynomial, Theoret. Comput. Sci., 36, 309-317, (1985) · Zbl 0565.68041  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  Lovász, László, Spectra of graphs with transitive groups, Period. Math. Hungar., 6, 2, 191-195, (1975) · Zbl 0395.05057  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  Nešetřil, Jaroslav, Homomorphisms of derivative graphs, Discrete Math., 1, 3, 257-268, (1971) · Zbl 0227.05109  Pak, Igor; Vilenchik, Dan, Constructing uniquely realizable graphs, Discrete Comput. Geom., 50, 4, 1051-1071, (2013) · Zbl 1280.05092  Roberson, David E., Homomorphisms of Strongly Regular Graphs, (2016), arXiv:1601.00969 · Zbl 1356.05156  Schrijver, Alexander, A comparison of the Delsarte and Lovász bounds, IEEE Trans. Inform. Theory, 25, 4, 425-429, (1979) · Zbl 0444.94009  Stahl, Saul, $$n$$-Tuple colorings and associated graphs, J. Combin. Theory Ser. B, 20, 2, 185-203, (1976) · Zbl 0293.05115  Ted Spence’s webpage: Strongly regular graphs on at most 64 vertices. http://www.maths.gla.ac.uk/ es/srgraphs.php.  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.