Acyclic edge chromatic number of outerplanar graphs |
| |
| Authors: | Jian‐Feng Hou Jian‐Liang Wu Gui‐Zhen Liu Bin Liu |
| |
| Institution: | 1. School of Mathematics, Shandong University, Jinan 250100, P.R. China;2. Center for Discrete Mathematics, Fuzhou University, Fuzhou 350002, P.R. China |
| |
| Abstract: | A proper edge coloring of a graph G is called acyclic if there is no 2‐colored cycle in G. The acyclic edge chromatic number of G, denoted by χ (G), is the least number of colors in an acyclic edge coloring of G. In this paper, we determine completely the acyclic edge chromatic number of outerplanar graphs. The proof is constructive and supplies a polynomial time algorithm to acyclically color the edges of any outerplanar graph G using χ (G) colors. © 2009 Wiley Periodicals, Inc. J Graph Theory 64: 22–36, 2010 |
| |
| Keywords: | acyclic edge coloring outerplanar graph |
|
|
