Hajnal, Andras


Unions of triangle free graphs ★★★

Author(s): Erdos; Hajnal

\begin{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? \end{problem}

Keywords: forbidden subgraph; infinite graph; triangle free

The Erdös-Hajnal Conjecture ★★★

Author(s): Erdos; Hajnal

\begin{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)}$. \end{conjecture}

Keywords: induced subgraph

Syndicate content