Vertex colorings without isolates
Vertex colorings without isolates
复制标题
DOI：
10.1016/0095-8956(79)90020-0
复制
发表时间：
1979-12
期刊：
影响因子：
--
通讯作者：
Stephen B. Maurer
中科院分区：
文献类型：
--
作者：
Stephen B. Maurer
如果顶点的所有相邻顶点的颜色都不同于它自己的颜色，则将顶点的顶点称为简单graphisolatedit。a . J. Goldman问过：什么时候可以把一个图的顶点涂成黑色，剩下的顶点涂成白色，这样就不会有孤立的顶点了？我们证明了(1)如果连通且最小次为2，则除非次为1，否则总是可能的；(2)如果gis是2连通的，则对于任意对（b,w）存在两个单色子图连通的着色；(3)如果顶点为1次，则a （b,w）无分离着色存在的必要条件是某个背包不等式存在解。接下来，提出了将(1)和(2)概括为颜色的陈述，并讨论了关于它们的真实性的当前知识。然后给出了较难表述和证明的(1)和(3)的各种改进。例如，对于(1)的假设，可以选择至少一个单色子图是连通的。在大多数情况下，式(3)的必要背包不等式是充分的。在整个过程中，我们考虑了不分离着色（如果可能的话）的算法复杂性。对于大多数可能在实践中出现的图，有一个有效的算法来解决两色问题。然而，对于任意图，2-（或更多）颜色问题是np完全的。
Call a vertex of a vertex-colored simple graphisolatedif all its neighbors have colors other than its own. A. J. Goldman has asked: When is it possible to colorbvertices of a graph black and the remainingwvertices white so that no vertex is isolated? We prove (1) ifGis connected and has minimum degree 2, it is always possible unlessborwis 1; (2) ifGis 2-connected, then for any pair (b,w) there is a coloring in which both monochromatic subgraphs are connected; (3) ifGhas vertices of degree 1, a necessary condition for a (b,w) coloring without isolates to exist is that there be a solution to a certain knapsack inequality. Next, statements generalizing (1) and (2) toncolors are presented, and current knowledge about their truth is discussed. Then various refinements of (1) and (3), more complicated to state and prove, are given. For instance, with the hypotheses of (1) at least one of the monochromatic subgraphs may be chosen to be connected. Also, the necessary knapsack inequality of (3) is, in most cases, sufficient. Throughout, some consideration is given to the algorithmic complexity of coloring (if possible) without isolates. For most graphs which might arise in practice there is an efficient algorithm for the 2-color problem. However, for arbitrary graphs the 2-(or more) color problem is NP-complete.