论文标题
关于强大着色问题的新结果
New results on the robust coloring problem
论文作者
论文摘要
经典图形着色模型的许多变化由于其多个应用而进行了深入研究。例如，安排问题和飞机作业，例如激励着色问题。该模型通过结合两种颜色提供的信息来捕获这些优化问题的自然限制：图形的顶点着色和其补体子图上的诱导边缘着色；目的是将图形的所有适当颜色以固定数量的颜色最小化，在子图中的边缘数量具有相同颜色的端点。强大着色模型的研究一直集中在使用至少三种颜色时，由于其NP-固有特征的搜索，但在其他方向上几乎没有取得进展。我们提出了一种有关问题的新方法，该问题获得了第一个一般图的非效法结果的集合； among them, we prove that robust coloring is the model that better approaches the equitable partition of the vertex set, even when the graph does not admit a so-called \emph{equitable coloring}.我们还向未解决的两种颜色的未解决情况显示了其决策问题的NP完整性，在相关的可靠着色参数上获得界限，并在路径上解决了一个猜想，以说明研究这种着色模型的复杂性。
Many variations of the classical graph coloring model have been intensively studied due to their multiple applications; scheduling problems and aircraft assignments, for instance, motivate the robust coloring problem. This model gets to capture natural constraints of those optimization problems by combining the information provided by two colorings: a vertex coloring of a graph and the induced edge coloring on a subgraph of its complement; the goal is to minimize, among all proper colorings of the graph for a fixed number of colors, the number of edges in the subgraph with the endpoints of the same color. The study of the robust coloring model has been focused on the search for heuristics due to its NP-hard character when using at least three colors, but little progress has been made in other directions. We present a new approach on the problem obtaining the first collection of non-heuristic results for general graphs; among them, we prove that robust coloring is the model that better approaches the equitable partition of the vertex set, even when the graph does not admit a so-called \emph{equitable coloring}. We also show the NP-completeness of its decision problem for the unsolved case of two colors, obtain bounds on the associated robust coloring parameter, and solve a conjecture on paths that illustrates the complexity of studying this coloring model.
