Acyclic Edge Chromatic Number of Outerplanar Graphs

被引：36
|
作者：
Hou, Jian-Feng [1 ,2 ]
Wu, Jian-Liang [1 ]
Liu, Gui-Zhen [1 ]
Liu, Bin [1 ]
机构：
[1] Shandong Univ, Sch Math, Jinan 250100, Peoples R China
[2] Fuzhou Univ, Ctr Discrete Math, Fuzhou 350002, Peoples R China
来源：
JOURNAL OF GRAPH THEORY | 2010年 / 64卷 / 01期
关键词：
acyclic; edge coloring; outerplanar graph; PLANAR GRAPHS; COLORINGS;
D O I：
10.1002/jgt.20436
中图分类号：
O1 [数学];
学科分类号：
0701 ; 070101 ;
摘要：
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 7(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 chi(a)'(G) colors. (C) 2009 Wiley Periodicals. Inc. J Graph Theory 64: 22-36, 2010
引用
收藏
页码：22 / 36
页数：15
相关论文
共 50 条
  • [1] Injective Chromatic Number of Outerplanar Graphs
    Mozafari-Nia, Mahsa
    Omoomi, Behnaz
    TAIWANESE JOURNAL OF MATHEMATICS, 2018, 22 (06): : 1309 - 1320
  • [2] The generalized acyclic edge chromatic number of random regular graphs
    Gerke, Stefanie
    Greenhill, Catherine
    Wormald, Nicholas
    JOURNAL OF GRAPH THEORY, 2006, 53 (02) : 101 - 125
  • [3] Acyclic list edge coloring of outerplanar graphs
    Shu, Qiaojun
    Wang, Yiqiao
    Wang, Weifan
    DISCRETE MATHEMATICS, 2013, 313 (03) : 301 - 311
  • [4] The relaxed game chromatic number of outerplanar graphs
    Dunn, C
    Kierstead, HA
    JOURNAL OF GRAPH THEORY, 2004, 46 (01) : 69 - 78
  • [5] On the packing chromatic number of subcubic outerplanar graphs
    Gastineau, Nicolas
    Holub, Premysl
    Togni, Olivier
    DISCRETE APPLIED MATHEMATICS, 2019, 255 : 209 - 221
  • [6] Relaxed game chromatic number of trees and outerplanar graphs
    He, WJ
    Wu, JJ
    Zhu, XD
    DISCRETE MATHEMATICS, 2004, 281 (1-3) : 209 - 219
  • [7] Directed Acyclic Outerplanar Graphs Have Constant Stack Number
    Jungeblut, Paul
    Merker, Laura
    Ueckerdt, Torsten
    2023 IEEE 64TH ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, FOCS, 2023, : 1937 - 1952
  • [8] A new bound on the acyclic edge chromatic number
    Fialho, Paula M. S.
    de Lima, Bernardo N. B.
    Procacci, Aldo
    DISCRETE MATHEMATICS, 2020, 343 (11)
  • [9] The r-acyclic chromatic number of planar graphs
    Wang, Guanghui
    Yan, Guiying
    Yu, Jiguo
    Zhang, Xin
    JOURNAL OF COMBINATORIAL OPTIMIZATION, 2015, 29 (04) : 713 - 722
  • [10] Strong Chromatic Index of Outerplanar Graphs
    Wang, Ying
    Wang, Yiqiao
    Wang, Weifan
    Cui, Shuyu
    AXIOMS, 2022, 11 (04)
12345