论文标题
公平的块图形数量的杂音 - 戈尔伯格类型界限
Vizing-Goldberg type bounds for the equitable chromatic number of block graphs
论文作者
论文摘要
图形$ g $的公平着色是$ g $的正确顶点着色，因此任何两种颜色类的大小最多都不同。在纸上，我们提出了一个猜想，该猜想提供了一个间隙，以限制每个块图形所需的最小颜色数量。换句话说，我们猜想的上限和下限之间的差异最多是一个。因此，从某种意义上说，这种情况类似于色素指数，在那里我们具有vible的经典定理和对多编码的Goldberg猜想。论文中获得的结果支持我们的猜想。更确切地说，我们在覆盖良好的块图中验证它，它们是每个顶点属于最大独立集的块图。我们还表明，对于块图而言，猜想是正确的，它包含一个不位于大于两个大小的独立集中的顶点。最后，我们验证了一些类似对称的块图的猜想。为了得出我们的结果，我们从这些类别获得了块图的结构特征。
An equitable coloring of a graph $G$ is a proper vertex coloring of $G$ such that the sizes of any two color classes differ by at most one. In the paper, we pose a conjecture that offers a gap-one bound for the smallest number of colors needed to equitably color every block graph. In other words, the difference between the upper and the lower bounds of our conjecture is at most one. Thus, in some sense, the situation is similar to that of chromatic index, where we have the classical theorem of Vizing and the Goldberg conjecture for multigraphs. The results obtained in the paper support our conjecture. More precisely, we verify it in the class of well-covered block graphs, which are block graphs in which each vertex belongs to a maximum independent set. We also show that the conjecture is true for block graphs, which contain a vertex that does not lie in an independent set of size larger than two. Finally, we verify the conjecture for some symmetric-like block graphs. In order to derive our results we obtain structural characterizations of block graphs from these classes.
