Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Forcing graph
open-in-new
<p>In <a href="/facts/Graph_theory/VVPCd4TX">graph theory</a>, a forcing graph is one whose density determines whether a graph sequence is quasi-random. The term was first coined by Chung, Graham, and Wilson in 1989. Forcing graphs play an important role in the study of <a href="/facts/Pseudorandom_graph/MIgCgsf0">pseudorandomness</a> in graph sequences. </p><p>The forcing conjecture states that the forcing graphs are exactly the cyclic bipartite graphs. It has been described as "one of the major open problems in <a href="/facts/Extremal_combinatorics/j9sVICGG">extremal combinatorics</a>". </p>