We prove that for , if is an -vertex graph with chromatic number but any its proper subgraph has smaller chromatic number, then contains at most copies of cliques of size . This answers a problem of Abbott and Zhou and provides a tight bound on a conjecture of Gallai. …
Katona's intersection theorem states that every intersecting family satisfies , where is the shadow of . Frankl conjectured that for and every intersecting family , there is some such that , where $\mathcal F(i)=\{F\setminus i:i\in F\in\mathcal …
The Structural Theorem of the Graph Minors series of Robertson and Seymour asserts that, for every there exists some constant such that every -minor-free graph admits a tree decomposition whose torsos can be transformed, by the removal of at most vertices, to graphs that can be seen as the union of some …
Van der Waerden's theorem states that any coloring of with a finite number of colors will contain arbitrarily long monochromatic arithmetic progressions. This motivates the definition of the van der Waerden number which is the smallest such that any -coloring of guarantees the presence of a monochromatic arithmetic progression of length …
