More Tales of Hoffman: bounds for the vector chromatic number of a graph

preprint2020arXivOpen access

Abstract

Let χ(G)χ(G) denote the chromatic number of a graph and χv(G)χ_v(G) denote the vector chromatic number. For all graphs χv(G)≤χ(G)χ_v(G) \le χ(G) and for some graphs χv(G)≪χ(G)χ_v(G) \ll χ(G). Galtman proved that Hoffman's well-known lower bound for χ(G)χ(G) is in fact a lower bound for χv(G)χ_v(G). We prove that two more spectral lower bounds for χ(G)χ(G) are also lower bounds for χv(G)χ_v(G). We then use one of these bounds to derive a new characterization of χv(G)χ_v(G).

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.