Cubical coloring — fractional covering by cuts and semidefinite programming
Robert Šámal
Abstract
We introduce a new graph parameter that measures fractional covering
of a graph by cuts. Besides being interesting in its own right, it is
useful for study of homomorphisms and tension-continuous mappings. We
study the relations with chromatic number, bipartite density, and
other graph parameters. We find the value of our parameter for a
family of graphs based on hypercubes. These graphs play for our
parameter the role that cliques play for the chromatic number and
Kneser graphs for the fractional chromatic number. The fact that the
defined parameter attains on these graphs the correct value suggests
that our definition is a natural one. In the proof we use the
eigenvalue bound for maximum cut and a recent result of Engström,
Färnqvist, Jonsson, and Thapper [An approximability-related
parameter on graphs 13; properties and applications, DMTCS
vol. 17:1, 2015, 33 13;66]. We also provide a polynomial time
approximation algorithm based on semidefinite programming and in
particular on vector chromatic number (defined by Karger, Motwani and
Sudan [Approximate graph coloring by semidefinite programming, J. ACM
45 (1998), no. 2, 246 13;265]).
Full Text: PDF PostScript