On Graph Associations
Landon Rabern · SIAM Journal on Discrete Mathematics · 2006
We introduce a notion of vertex association and consider sequences of these associations. This allows for slick proofs of a few known theorems as well as showing that for any induced subgraph H of G, chi(G) \leq chi(H) + 1/2 (omega (G) + |G| - |H| - 1). As a special case of this, we have chi(G) \leq \lceil omega(G) + tau(G) / 2 \rceil (here chi(G) denotes the chromatic number, omega(G) the clique number, and tau(G) the vertex cover number), which is a generalization of the Nordhaus--Gaddum upper bound. In addition, this settles a conjecture of Reed that chi(G) \leq \lceil omega(G) + Delta(G) + 1 / 2 \rceil in the case when delta(\overline G) \leq omega(\overline G).