Hajnal, Andras

Unions of triangle free graphs ★★★

Author(s): Erdos; Hajnal

Problem   Does there exist a graph with no subgraph isomorphic to $ K_4 $ which cannot be expressed as a union of $ \aleph_0 $ triangle free graphs?

Keywords: forbidden subgraph; infinite graph; triangle free

The Erdös-Hajnal Conjecture ★★★

Author(s): Erdos; Hajnal

Conjecture   For every fixed graph $ H $, there exists a constant $ \delta(H) $, so that every graph $ G $ without an induced subgraph isomorphic to $ H $ contains either a clique or an independent set of size $ |V(G)|^{\delta(H)} $.

Keywords: induced subgraph

Syndicate content