论文标题
带有自动放电的方形着色平面图
Square coloring planar graphs with automatic discharging
论文作者
论文摘要
排放方法是一种有力的证明技术，尤其是对于图形着色问题。它的主要缺点是，它通常需要冗长的案例分析，有时将其提供给计算机进行验证。但是，使用计算机积极寻找放电的证明是不那么普遍的。在本文中，我们使用线性编程方法自动寻找证明。虽然我们的系统并非完全自主，但我们设法在韦格纳的猜想方面取得了一些进步，距离$ 2 $平面图的着色，表明$ 12 $的颜色足以以距离$ 2 $ $ 2 $每个平面图，最高度为4 $。
The discharging method is a powerful proof technique, especially for graph coloring problems. Its major downside is that it often requires lengthy case analyses, which are sometimes given to a computer for verification. However, it is much less common to use a computer to actively look for a discharging proof. In this paper, we use a Linear Programming approach to automatically look for a discharging proof. While our system is not entirely autonomous, we manage to make some progress towards Wegner's conjecture for distance-$2$ coloring of planar graphs, by showing that $12$ colors are sufficient to color at distance $2$ every planar graph with maximum degree $4$.
