Acyclic Edge Coloring of IC-planar Graphs
- PDF / 176,346 Bytes
- 9 Pages / 612 x 792 pts (letter) Page_size
- 68 Downloads / 197 Views
Acta Mathemacae Applicatae Sinica, English Series The Editorial Office of AMAS & Springer-Verlag GmbH Germany 2020
Acyclic Edge Coloring of IC-planar Graphs Wen-yao SONG1,∗ , Yuan-yuan DUAN1,† , Juan WANG2 , Lian-ying MIAO2 1 School
of Mathematics and Statistics, Zaozhuang University, Zaozhuang 277160, China
(E-mail: ∗ [email protected], † [email protected]) 2 School of Mathematics, China University of Mining and Technology, Xuzhou 221116, China
Abstract A proper edge coloring of a graph G is acyclic if there is no 2-colored cycle in G. The acyclic chromatic index of G is the least number of colors such that G has an acyclic edge coloring and denoted by χ′a (G). An IC-plane graph is a topological graph where every edge is crossed at most once and no two crossed edges share a vertex. In this paper, it is proved that χ′a (G) ≤ ∆(G) + 10, if G is an IC-planar graph without adjacent triangles and χ′a (G) ≤ ∆(G) + 8, if G is a triangle-free IC-planar graph. Keywords
Acyclic chromatic index; acyclic edge coloring; IC-planar graph
2000 MR Subject Classification
1
05C15
Introduction
All graphs considered are finite, simple and undirected. Let G be a graph. We use V (G), E(G), ∆(G) and δ(G) to denote its vertex set, edge set, maximum degree and minimum degree, respectively. For a planar graph G, F (G) denotes its face set, d(v) denotes the degree of a vertex v in G. The length or degree of a face f , denoted by d(f ), is the length of the boundary walk of f in G. We call v a k-vertex, or a k + -vertex, or a k − -vertex if d(v) = k, or d(v) ≥ k, or d(v) ≤ k, respectively and call f a k-face, or a k + -face, or a k − -face if d(f ) = k, or d(f ) ≥ k, or d(f ) ≤ k, respectively. Any undefined notation follows that of Bondy and Murty[6] . A proper edge k-coloring of a graph G is a mapping ϕ : E(G) → {1, 2, · · · , k} such that no pair of adjacent edges are colored with the same color. A proper edge coloring of a graph G is acyclic if there is no 2-colored cycle in G. The acyclic chromatic index of G is the least number of colors such that G has an acyclic edge coloring and denoted by χ′a (G). Fiamˇcik[9] and later Alon et al.[3] proposed the following conjecture: Conjecture 1. For any graph G, χ′a (G) ≤ ∆(G) + 2. Alon et al.[2] proved that χ′a (G) ≤ 64∆(G) for any graph G. Molloy and Reed[18] improved this bound to that χ′a (G) ≤ 16∆(G). Nˇesetˇril and Wormald[20] proved that χ′a (G) ≤ ∆(G) + 1 for a random ∆(G)-regular graph G. The acyclic edge coloring of some special classes of graphs has been studied widely, including graphs with maximum degree 4 (Basavaraju and Chandran[4] ), graphs with large girths (Lin et al.[17] ), subcubic graphs (Basavaraju and Chandran[5] ; Fiamˇcik[9] ; Skulrattanakulchai[23] ), series-parallel graphs (Hou et al.[13] ; Wang and Shu[26] ), outerplanar graphs (Hou et al.[14] ; Muthu et al.[19] ), planar graphs (Cohen et al.[7] ; Dong and Xu[8] ; Fiedorowicz et al.[10] ; Guan et al.[11] ; Hou et al.[12] ; Shu and Wang[21, 22] ; Wang et al.[27] ; Yu et al.[29] ) and 1-planar graphs (Chen
Data Loading...
