Three-rainbow coloring of split graphs

被引：0
|
作者：
Hu Y. [1 ]
Liu T. [1 ]
机构：
[1] School of Sciences, Tianjin University, Tianjin
来源：
Transactions of Tianjin University | 2015年 / 21卷 / 03期
基金：
中国国家自然科学基金;
关键词：
3-rainbow coloring; algorithm; edge coloring; split graph;
D O I：
10.1007/s12209-015-2431-y
中图分类号：
学科分类号：
摘要：
After a necessary condition is given, 3-rainbow coloring of split graphs with time complexity O(m) is obtained by constructive method. The number of corresponding colors is at most 2 or 3 more than the minimum number of colors needed in a 3-rainbow coloring. © 2015, Tianjin University and Springer-Verlag Berlin Heidelberg.
引用
收藏
页码：284 / 287
页数：3
相关论文
共 50 条
  • [41] Edge coloring nearly bipartite graphs
    Reed, B
    OPERATIONS RESEARCH LETTERS, 1999, 24 (1-2) : 11 - 14
  • [42] Strong Edge Coloring of Cayley Graphs and Some Product Graphs
    Dara, Suresh
    Mishra, Suchismita
    Narayanan, Narayanan
    Tuza, Zsolt
    GRAPHS AND COMBINATORICS, 2022, 38 (02)
  • [43] Improved edge-coloring with three colors
    Kowalik, Lukasz
    THEORETICAL COMPUTER SCIENCE, 2009, 410 (38-40) : 3733 - 3742
  • [44] Rainbow Connections of Graphs: A Survey
    Xueliang Li
    Yongtang Shi
    Yuefang Sun
    Graphs and Combinatorics, 2013, 29 : 1 - 38
  • [45] Rainbow Connections of Graphs: A Survey
    Li, Xueliang
    Shi, Yongtang
    Sun, Yuefang
    GRAPHS AND COMBINATORICS, 2013, 29 (01) : 1 - 38
  • [46] More on the Rainbow Disconnection in Graphs
    Bai, Xuqing
    Chang, Renying
    Huang, Zhong
    Li, Xueliang
    DISCUSSIONES MATHEMATICAE GRAPH THEORY, 2022, 42 (04) : 1185 - 1204
  • [47] The Rainbow Connection Number of Origami Graphs and Pizza Graphs
    Nabila, S.
    Salman, A. N. M.
    2ND INTERNATIONAL CONFERENCE OF GRAPH THEORY AND INFORMATION SECURITY, 2015, 74 : 162 - 167
  • [48] Edge-colorings of graphs avoiding complete graphs with a prescribed coloring
    Benevides, Fabricio S.
    Hoppen, Carlos
    Sampaio, Rudini M.
    DISCRETE MATHEMATICS, 2017, 340 (09) : 2143 - 2160
  • [49] On total and edge coloring some Kneser graphs
    C. M. H. de Figueiredo
    C. S. R. Patrão
    D. Sasaki
    M. Valencia-Pabon
    Journal of Combinatorial Optimization, 2022, 44 : 119 - 135
  • [50] Edge Coloring of Embedded Graphs with Large Girth
    Xuechao Li
    Rong Luo
    Graphs and Combinatorics, 2003, 19 : 393 - 401
12345