Independence and graph homomorphisms graph homomorphisms
Copyright policy )Independence and graph homomorphisms graph homomorphisms
AbstractA 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 (3n)/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 2k+1, and minimum degree exceeding n/(k+1) contains an independent set with at least kn/(2k+1) vertices; however, we suspect this is not best possible. © 1993 John Wiley & Sons, Inc.
- Smith College United States
Extremal problems in graph theory, independent set, cycle, triangle, graph homomorphisms, Paths and cycles, no homomorphism lemma, minimum degree
Extremal problems in graph theory, independent set, cycle, triangle, graph homomorphisms, Paths and cycles, no homomorphism lemma, minimum degree
citations This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).5 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Average influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Average impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Average
Citations provided by BIP!Popularity provided by BIP!