The No-Homomorphism Lemma
by
Karen L. Collins
Wesleyan University
Coauthors: Zhongyuan Che (Wesleyan University)

Let G be a graph and chi(G) be its chromatic number, that is, the smallest integer k so that the vertices of G can be colored with k colors so that any two adjacent vertices are colored differently. Let Delta_i(G) be the size of the largest i-colorable subgraph of G for 1 <= i <= chi(G). The chromatic difference sequence of G is alpha₁(G), alpha₂(G), ... , alpha_chi(G)(G) where alpha₁(G) = Delta₁(G) and alpha_i(G) = Delta_i(G)-Delta_i-1(G) for 2 <= i <= chi(G). If G has n vertices, the normalized chromatic difference sequence of G is defined to be [(alpha₁(G))/n], [(alpha₂(G))/n], ... , [(alpha_chi(G)(G))/n]. The original No-Homomorphism Lemma states that if a graph G maps homomorphically to a vertex transitive graph H, then the normalized chromatic difference sequence of G must dominate the normalized chromatic difference sequence of H.

We present the improved No-Homomorphism Lemma. Let P be a graph property such that if G --> H and H has property P, then G has property P. There are two canonical examples of such properties P. Fix a graph T. Then the first is the property that G maps to T, and the second is the property that T does not map to G. Let beta_P(G) equal the size of the largest induced subgraph of G with property P. For any graph G and any vertex transitive graph H, if G --> H, then

betaP(G) |V(G)| >=  betaP(H) |V(H)| .

http://kcollins.web.wesleyan.edu/

Date received: April 19, 2001