This paper proposes two self-stabilizing algorithms for acyclic colorings of graphs. An acyclic coloring of a graph G is a coloring of the vertices of G such that the vertices with the same color in G induces an acyclic subgraph. The first algorithm we proposed needs 2 colors for a complete bipartite graph, or less than l+D/2 colors for a general graph, where D is the degree of G. Both graphs must be acyclic oriented in advance. In some special acyclic orientation, it needs only 3 colors for a planar graph, or a K3,3-free or K5-free graph. The second algorithm we proposed is for a K4-free and rooted graph, and it needs only 2 colors.
展开▼
机译：本文提出了两个用于图形的无循环着色的自稳定算法。曲线图G的无循环着色是G的顶点的着色，使得具有相同颜色的顶点的顶点诱导非环状子图。我们提出的第一算法需要2种颜色的完整的二分图，或者对于一般图的L + D / 2颜色，其中D是G的程度。这两条图必须预先取向无环。在一些特殊的无循环方向上，它仅需要平面图的3种颜色，或无K 3,3或无k5图形。我们提出的第二种算法是用于无K4和扎根的图形，它只需要2种颜色。
展开▼
