没有K_5-子式的图是无圈5-可染的

2006年,Borodin证明了所有平面图都可以无圈5-可染。本文推广Borodin的结果到没有K5-子式的图。

图中的圈不可分离性(英文)

如果对图中的两条边或两个顶点,存在两个顶点不交圈分别包含他们,那么这两条边或两个顶点叫做可用圈分离。不能用圈分离的边对或点对叫做圈不可分离的。定义了包含一对不可用圈分离的边的图的一个无穷类。给出了两个顶点或两条边不可用圈分离的一个简单的充分条件。这个无穷类包含Wagner图作为元素。提出了关于所定义的概念和图类的一些尚未解决的研究问题。