论文标题
图形图中公平着色问题的理论和算法方面
Graph theoretic and algorithmic aspect of the equitable coloring problem in block graphs
论文作者
论文摘要
图形$ g =（v，e）$的公平着色是$ g $的（适当的）顶点颜色，因此任何两个颜色类的尺寸最多都不同。在本文中，我们考虑了块图中的公平着色问题。回想一下，后者是每个2相互连接的组件是完整的图形的图。在块图的类别中，问题仍然很困难。在本文中，我们提出了一些与各种参数有关的理论结果。然后，我们使用它们来追踪一些算法含义，主要处理问题的固定参数障碍。
An equitable coloring of a graph $G=(V,E)$ is a (proper) vertex-coloring of $G$, such that the sizes of any two color classes differ by at most one. In this paper, we consider the equitable coloring problem in block graphs. Recall that the latter are graphs in which each 2-connected component is a complete graph. The problem remains hard in the class of block graphs. In this paper, we present some graph theoretic results relating various parameters. Then we use them in order to trace some algorithmic implications, mainly dealing with the fixed-parameter tractability of the problem.
