44 citations · 279 across the 33 of their papers we have counts for
Showing 2007Show all
2 papers · 1 filter
math.CO2007
Induced trees in triangle-free graphs
Jiri Matousek, Robert Samal
We prove that every connected triangle-free graph on vertices contains an induced tree on vertices, where is a positive constant. The best known uppe…
math.CO2007★ 1 cited
Graph coloring with no large monochromatic components
N. Linial, J. Matousek, O. Sheffet +1
For a graph G and an integer t we let mcc_t(G) be the smallest m such that there exists a coloring of the vertices of G by t colors with no monochromatic connected subgraph having…