35 citations · 45 across the 3 of their papers we have counts for
Showing math.COShow all
3 papers · 1 filter
math.CO2005★ 10 cited
Bounded-Degree Graphs have Arbitrarily Large Geometric Thickness
Janos Barat, Jiri Matousek, David R. Wood
The geometric thickness of a graph G is the minimum integer k such that there is a straight line drawing of G with its edge set partitioned into k plane subgraphs. Eppstein [Separa…
math.CO2003
Expected length of the longest common subsequence for large alphabets
Marcos Kiwi, Martin Loebl, Jiri Matousek
We consider the length L of the longest common subsequence of two randomly uniformly and independently chosen n character words over a k-ary alphabet. Subadditivity arguments yield…
math.CO2002★ 35 cited
Topological lower bounds for the chromatic number: A hierarchy
Jiri Matousek, Günter M. Ziegler
This paper is a study of ``topological'' lower bounds for the chromatic number of a graph. Such a lower bound was first introduced by Lovász in 1978, in his famous proof of the \em…