Packing and Covering Triangles in K4-free Planar Graphs
Packing and Covering Triangles in K4-free Planar Graphs
复制标题
DOI：
10.1007/s00373-011-1071-9
复制
发表时间：
2012-09
影响因子：
0.7
通讯作者：
P. Haxell;A. Kostochka;Stéphan Thomassé
中科院分区：
文献类型：
--
作者：
P. Haxell;A. Kostochka;Stéphan Thomassé
我们证明了每一个不含ν边不交三角形的无K4平面图都包含一组不含边不交三角形的图，去掉这些边不交的平面图就不含边。此外，只有当G是5个轮子的边不相交的并，并可能加上一些不在三角形中的边时，才能达到相等。我们还证明，如果我们不考虑平面图，而是考虑每条边至多属于两个三角形的图类，同样的说法也是正确的。相反，对于任一图2，都有最多包含ν边不相交三角形的无K4图，它们需要多于c条ν边才能覆盖所有三角形。
We show that everyK4-free planar graph with at mostνedge-disjoint triangles contains a set of at mostedges whose removal makes the graph triangle-free. Moreover, equality is attained only whenGis the edge-disjoint union of 5-wheels plus possibly some edges that are not in triangles. We also show that the same statement is true if instead of planar graphs we consider the class of graphs in which each edge belongs to at most two triangles. In contrast, it is known that for anyc< 2 there areK4-free graphs with at mostνedge-disjoint triangles that need more thancνedges to cover all triangles.