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 条
  • [41] Edge covering pseudo-outerplanar graphs with forests
    Zhang, Xin
    Liu, Guizhen
    Wu, Jian-Liang
    DISCRETE MATHEMATICS, 2012, 312 (18) : 2788 - 2799
  • [42] Drawing outerplanar graphs using thirteen edge lengths
    Bakhajian Z.
    Feldheim O.N.
    Computational Geometry: Theory and Applications, 2023, 110
  • [43] PRECISE UPPER BOUND FOR THE STRONG EDGE CHROMATIC NUMBER OF SPARSE PLANAR GRAPHS
    Borodin, Oleg V.
    Ivanova, Anna O.
    DISCUSSIONES MATHEMATICAE GRAPH THEORY, 2013, 33 (04) : 759 - 770
  • [44] On b-acyclic chromatic number of a graph
    Anholcer, Marcin
    Cichacz, Sylwia
    Peterin, Iztok
    COMPUTATIONAL & APPLIED MATHEMATICS, 2023, 42 (01)
  • [45] Improved bounds on the generalized acyclic chromatic number
    Yu-wen Wu
    Kan-ran Tan
    Gui-ying Yan
    Acta Mathematicae Applicatae Sinica, English Series, 2016, 32 : 67 - 72
  • [46] Improved Bounds on the Generalized Acyclic Chromatic Number
    Wu, Yu-wen
    Tan, Kan-ran
    Yan, Gui-ying
    ACTA MATHEMATICAE APPLICATAE SINICA-ENGLISH SERIES, 2016, 32 (01): : 67 - 72
  • [47] A note on Vizing's independence number conjecture of edge chromatic critical graphs
    Luo, Rong
    Zhao, Yue
    DISCRETE MATHEMATICS, 2006, 306 (15) : 1788 - 1790
  • [48] Improved Bounds on the Generalized Acyclic Chromatic Number
    Yu-wen WU
    Kan-ran TAN
    Gui-ying YAN
    Acta Mathematicae Applicatae Sinica, 2016, 32 (01) : 67 - 72
  • [49] On the Maximum Number of Cycles in Outerplanar and Series–Parallel Graphs
    Anna de Mier
    Marc Noy
    Graphs and Combinatorics, 2012, 28 : 265 - 275
  • [50] On graphs with maximum difference between game chromatic number and chromatic number
    Hollom, Lawrence
    DISCRETE MATHEMATICS, 2025, 348 (02)
12345