Local conditions for planar graphs of acyclic edge coloring
Tóm tắt
Give a graph G, we color its all edges. If any two adjacent edges gets the different colors, then we call this color a proper edge coloring of G. Give a proper edge coloring of G, if only two colors alternately appear on a cycle, then the cycle is called bichromatic. Acyclic edge coloring of a graph G means that there are no bichromatic cycles in G. The acyclic chromatic index of a graph G is the minimum number k such that G has an acyclic edge coloring using k colors. Denoted
$${\chi ^{'}_a}(G)$$
as the acyclic chromatic index of G. A planar graph is a graph that can be embedded in the plane in such a way that no two edges intersect geometrically except at a vertex to which they are both incident. In this paper, we use the discharging method to prove that
$${\chi ^{'}_a}(G)\le \varDelta (G)+ 2$$
if G is a planar graph and there is an integer
$$k_v \in \{3, 4, 5\}$$
such that v is not contained in any
$$k_v$$
-cycle for every vertex v.
Tài liệu tham khảo
Fiamčik, J.: The acyclic chromatic class of graphs. Math. Slovaca 28, 139–145 (1978). ((in Russian))
Skulrattanakulchai, S.: Acyclic colorings of subcubic graphs. Inf. Process. Lett. 92, 161–167 (2004)
Venkateswarlu, A., Sarkar, S.: On acyclic edge-coloring of the complete bipartite graphs \(K_{(2p-1,2p-1)}\) for odd prime p. Discrere Math. 339, 72–77 (2016)