3 papers
math.CO2013
Maximum planar subgraphs in dense graphs
Peter Allen, Jozef Skokan, Andreas Würfl
Kühn, Osthus and Taraz showed that for each γ>0 there exists C such that any n-vertex graph with minimum degree γn contains a planar subgraph with at least 2n-C edges. We find the…
math.CO2011
Perfect graphs of fixed density: counting and homogenous sets
Julia Böttcher, Anusch Taraz, Andreas Würfl
For c in [0,1] let P_n(c) denote the set of n-vertex perfect graphs with density c and C_n(c) the set of n-vertex graphs without induced C_5 and with density c. We show that log|P_…
math.CO2009
Bandwidth, expansion, treewidth, separators, and universality for bounded degree graphs
Julia Böttcher, Klaas P. Pruessmann, Anusch Taraz +1
We establish relations between the bandwidth and the treewidth of bounded degree graphs G, and relate these parameters to the size of a separator of G as well as the size of an exp…