加权独立横断面和强着色算法

作者：David Harris

摘要：具有给定顶点划分的图中的独立横截(IT)是由每个划分类中的一个顶点组成的独立集。在具有给定顶点划分的给定图中，已知了IT存在的几个充分条件，这些条件多年来一直用于解决许多组合问题。其中一些IT存在定理有算法证明，但非构造性结果给出的最佳界与有效算法得到的最佳界之间还存在一定的差距。

最近，Graf和Haxell(2018)描述了一种新的(确定性)算法，它渐进地缩小了这一差距，但其适用性受到限制。本文提出了一种适用范围更广的随机化算法，并通过给出两个图的强色数问题的有效算法，说明了该算法的应用。

原文标题：Title:Algorithms for weighted independent transversals and strong colouring

地址：https://arxiv.org/abs/1907.00033