Please use this identifier to cite or link to this item:
Title: Vector coloring the categorical product of graphs
Authors: Godsil, Chris
Roberson, David E.
Rooney, Brendan
Šámal, Robert
Varvitsiotis, Antonios
Keywords: Science::Mathematics
Issue Date: 2019
Source: Godsil, C., Roberson, D. E., Rooney, B., Šámal, R., & Varvitsiotis, A. (2020). Vector coloring the categorical product of graphs. Mathematical Programming, 182(1-2), 275-314. doi:10.1007/s10107-019-01393-0
Journal: Mathematical Programming
Abstract: A vector t-coloring of a graph is an assignment of real vectors p1, … , pn to its vertices such that piTpi=t-1, for all i= 1 , … , n and piTpj≤-1, whenever i and j are adjacent. The vector chromatic number of G is the smallest number t≥ 1 for which a vector t-coloring of G exists. For a graph H and a vector t-coloring p1, … , pn of G, the map taking (i, ℓ) ∈ V(G) × V(H) to pi is a vector t-coloring of the categorical product G× H. It follows that the vector chromatic number of G× H is at most the minimum of the vector chromatic numbers of the factors. We prove that equality always holds, constituting a vector coloring analog of the famous Hedetniemi Conjecture from graph coloring. Furthermore, we prove necessary and sufficient conditions under which all optimal vector colorings of G× H are induced by optimal vector colorings of the factors. Our proofs rely on various semidefinite programming formulations of the vector chromatic number and a theory of optimal vector colorings we develop along the way, which is of independent interest.
ISSN: 0025-5610
DOI: 10.1007/s10107-019-01393-0
Schools: School of Physical and Mathematical Sciences 
Rights: © 2019 Springer-Verlag GmbH Germany, part of Springer Nature and Mathematical Optimization Society. This is a post-peer-review, pre-copyedit version of an article published in Mathematical Programming. The final authenticated version is available online at:
Fulltext Permission: open
Fulltext Availability: With Fulltext
Appears in Collections:SPMS Journal Articles

Files in This Item:
File Description SizeFormat 
Vector coloring the categorical product of graphs.pdf424.44 kBAdobe PDFThumbnail

Citations 50

Updated on May 27, 2023

Web of ScienceTM
Citations 50

Updated on Jun 1, 2023

Page view(s)

Updated on May 31, 2023

Download(s) 50

Updated on May 31, 2023

Google ScholarTM




Items in DR-NTU are protected by copyright, with all rights reserved, unless otherwise indicated.