Graph homomorphisms via vector colorings

DOI10.1016/j.ejc.2019.04.001zbMath1414.05199arXiv1610.10002OpenAlexW2962736919WikidataQ127960220 ScholiaQ127960220MaRDI QIDQ2422244

David E. Roberson, Robert Šámal, Antonios Varvitsiotis, Brendan Rooney, Chris D. Godsil

Publication date: 18 June 2019

Published in: European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1610.10002

zbMATH Keywords

Taylor graphsKneser graph

Mathematics Subject Classification ID

Semidefinite programming (90C22) Coloring of graphs and hypergraphs (05C15) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items (5)

The core of a complementary prism ⋮ Vector coloring the categorical product of graphs ⋮ Homomorphisms of strongly regular graphs ⋮ Spectral lower bounds for the orthogonal and projective ranks of a graph ⋮ More tales of Hoffman: bounds for the vector chromatic number of a graph

Uses Software

• SageMath

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Constructing uniquely realizable graphs
• The core of a graph
• Colouring lines in projective space
• Fast algorithms for the characteristic polynomial
• On the complexity of H-coloring
• n-tuple colorings and associated graphs
• Spectra of Cayley graphs
• Spectra of graphs with transitive groups
• Sabidussi versus Hedetniemi for three variations of the chromatic number
• Universal completability, least eigenvalue frameworks, and vector colorings
• Positive semidefinite matrix completion, universal rigidity and the strong Arnold property
• Homomorphisms of derivative graphs
• Erdős–Ko–Rado Theorems: Algebraic Approaches
• Approximate graph coloring by semidefinite programming
• A comparison of the Delsarte and Lovász bounds
• CORES OF SYMMETRIC GRAPHS
• Homomorphisms of strongly regular graphs

This page was built for publication: Graph homomorphisms via vector colorings