Journal article
Vector coloring the categorical product of graphs
University of Waterloo1
Algorithms and Logic, Department of Applied Mathematics and Computer Science, Technical University of Denmark2
Department of Applied Mathematics and Computer Science, Technical University of Denmark3
Korea Advanced Institute of Science and Technology4
Charles University5
Nanyang Technological University6
A vector t-coloring of a graph is an assignment of real vectors p 1 , … , p n 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 p 1 , … , p n of G, the map taking (i, ℓ) ∈ V(G) × V(H) to p i 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.
Language: | English |
---|---|
Publisher: | Springer Berlin Heidelberg |
Year: | 2019 |
Pages: | 275-314 |
Journal subtitle: | A Publication of the Mathematical Optimization Society |
ISSN: | 14364646 and 00255610 |
Types: | Journal article |
DOI: | 10.1007/s10107-019-01393-0 |
ORCIDs: | Roberson, David E. |
Categorical graph product Hedetniemi’s conjecture Lovász ϑ number Semidefinite programming Vector coloring
05C15 05C76 90C22 Lovász ϑ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\vartheta $$\end{document} number