Hajnal, Andras


Multicolour Erdős--Hajnal Conjecture ★★★

Author(s): Erdos; Hajnal

Conjecture   For every fixed $ k\geq2 $ and fixed colouring $ \chi $ of $ E(K_k) $ with $ m $ colours, there exists $ \varepsilon>0 $ such that every colouring of the edges of $ K_n $ contains either $ k $ vertices whose edges are coloured according to $ \chi $ or $ n^\varepsilon $ vertices whose edges are coloured with at most $ m-1 $ colours.

Keywords: ramsey theory

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