Independence and graph homomorphisms graph homomorphisms

1993/11/01 by Michael O. Albertson, Lily Chan, Ruth Haas
Computer Science · Mathematics · #Advanced Graph Theory Research #Advanced Topology and Set Theory #Combinatorics #Discrete mathematics #Graph #Graph homomorphism #Graph power #Homomorphism #Independent set #Lemma (botany) #Limits and Structures in Graph Theory #Line graph #Mathematics #Wheel graph

paper · doi:10.1002/jgt.3190170503

openalex publication_date 1993/11/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/25

Abstract

Abstract A graph with n vertices that contains no triangle and no 5‐cycle and minimum degree exceeding n /4 contains an independent set with at least (3 n )/7 vertices. This is best possible. The proof proceeds by producing a homomorphism to the 7‐cycle and invoking the No Homomorphism Lemma. For k ≥ 4, a graph with n vertices, odd girth 2 k +1, and minimum degree exceeding n /( k +1) contains an independent set with at least kn /(2 k +1) vertices; however, we suspect this is not best possible. © 1993 John Wiley & Sons, Inc.

Citations

• On the connection between chromatic number, maximal clique and minimal degree of a graph

Related

• The homotopy type of the independence complex of graphs with no induced cycles of length divisible by 3
• Independence Equivalence Classes of Paths and Cycles
• Independence number in triangle-free graphs avoiding a minor
• On the order of countable graphs
• Asymmetric results about graph homomorphisms