标题： 诱导泛图的下界 显示英文标题

标题： Lower Bounds for Induced-Universal Graphs

摘要： 我们给出了一系列新的下界，关于包含给定家族中每个图作为诱导子图所需的图的最小顶点数。 特别是，我们证明了对于$n$顶点的平面图来说，这个诱导全图必须至少有$10.52n$个顶点。 我们还证明了为了打破这个下界，需要考虑的冲突图的数量至少为$137$。 换句话说，任何少于$137$个具有$n$个顶点的平面图家族都有一个具有少于$10.52n$个顶点的诱导全图，这强调了打破这种下界所面临的困难。 对于其他图家族，包括但不限于树、外平面图、系列-并行图、$K_{3,3}$-无关图，也得出了类似的结果。 As a byproduct, we show that any family of $t$ graphs of $n$ vertices having small chromatic number and sublinear pathwidth, like any proper minor-closed family, has an induced-universal graph with less than $\frac{15}{7} \sqrt{t} \cdot n$ vertices. This is achieved by making a bridge between equitable colorings, combinatorial designs, and path-decompositions. 显示英文摘要

摘要： We give a series of new lower bounds on the minimum number of vertices required by a graph to contain every graph of a given family as induced subgraph. In particular, we show that this induced-universal graph for $n$-vertex planar graphs must have at least $10.52n$ vertices. We also show that the number of conflicting graphs to consider in order to beat this lower bound is at least $137$. In other words, any family of less than $137$ planar graphs of $n$ vertices has an induced-universal graph with less than $10.52n$ vertices, stressing the difficulty in beating such lower bounds. Similar results are developed for other graph families, including but not limited to, trees, outerplanar graphs, series-parallel graphs, $K_{3,3}$-minor free graphs. As a byproduct, we show that any family of $t$ graphs of $n$ vertices having small chromatic number and sublinear pathwidth, like any proper minor-closed family, has an induced-universal graph with less than $\frac{15}{7} \sqrt{t} \cdot n$ vertices. This is achieved by making a bridge between equitable colorings, combinatorial designs, and path-decompositions.