As one of the first applications of the polynomial method in combinatorics, Alon and Tarsi gave a way to prove that a graph is choosable (colorable from any lists of prescribed size). We describe an efficient way to implement this approach, making it feasible to test choosability of graphs with around 70 edges. We also show that in case that Alon-Tarsi method fails to show that the graph is choosable, further coefficients of the graph polynomial provide constraints on the list assignments from which the graph cannot be colored. This often enables us to confirm colorability from a given list assignment, or to decide choosability by testing just a few list assignments. The implementation can be found at https://gitlab.mff.cuni.cz/dvorz9am/alon-tarsi-method.
翻译:作为多种混合方法在组合法中的首批应用之一,Alon和Tarsi提供了一种方法,以证明图表是可挑剔的(从任何指定大小的列表中可以色化的)。我们描述了一种有效的方法来实施这一方法,从而可以测试大约70边缘的图形的可选性。我们还表明,如果Alon-Tarsi方法未能显示该图是可挑剔的,那么图多面性的其他系数为无法绘制图表的列表任务提供了限制。这往往使我们能够确认某个特定列表任务中的可色性,或者通过测试少数列表任务来决定可选性。 可在https://gitlab.mff.cuni.cz/dvorz9am/alon-tarsi-method上找到实施方法。