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 条
  • [21] The edge chromatic number of outer-1-planar graphs
    Zhang, Xin
    DISCRETE MATHEMATICS, 2016, 339 (04) : 1393 - 1399
  • [22] On the Geometric Ramsey Number of Outerplanar Graphs
    Cibulka, Josef
    Gao, Pu
    Krcal, Marek
    Valla, Tomas
    Valtr, Pavel
    DISCRETE & COMPUTATIONAL GEOMETRY, 2015, 53 (01) : 64 - 79
  • [23] The incidence coloring number of Halin graphs and outerplanar graphs
    Wang, SD
    Chen, DL
    Pang, SC
    DISCRETE MATHEMATICS, 2002, 256 (1-2) : 397 - 405
  • [24] Acyclic chromatic index of chordless graphs
    Basavaraju, Manu
    Hegde, Suresh Manjanath
    Kulamarva, Shashanka
    DISCRETE MATHEMATICS, 2023, 346 (08)
  • [25] Acyclic List Edge Coloring of Graphs
    Lai, Hsin-Hao
    Lih, Ko-Wei
    JOURNAL OF GRAPH THEORY, 2013, 72 (03) : 247 - 266
  • [26] An Upper Bound for the Adjacent Vertex Distinguishing Acyclic Edge Chromatic Number of a Graph
    Liu, Xin-sheng
    An, Ming-qiang
    Gao, Yang
    ACTA MATHEMATICAE APPLICATAE SINICA-ENGLISH SERIES, 2009, 25 (01): : 137 - 140
  • [27] On Chromatic Number of Colored Mixed Graphs
    Das, Sandip
    Nandi, Soumen
    Sen, Sagnik
    ALGORITHMS AND DISCRETE APPLIED MATHEMATICS, 2017, 10156 : 130 - 140
  • [28] The edge-distinguishing chromatic number of petal graphs, chorded cycles, and spider graphs
    Fickes, Grant
    Wong, Tony W. H.
    ELECTRONIC JOURNAL OF GRAPH THEORY AND APPLICATIONS, 2022, 10 (02) : 393 - 414
  • [29] On the Maximum Number of Cycles in Outerplanar and Series-Parallel Graphs
    de Mier, Anna
    Noy, Marc
    GRAPHS AND COMBINATORICS, 2012, 28 (02) : 265 - 275
  • [30] A New Upper Bound for the Independence Number of Edge Chromatic Critical Graphs
    Luo, Rong
    Zhao, Yue
    JOURNAL OF GRAPH THEORY, 2011, 68 (03) : 202 - 212
12345