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 条
  • [21] Rainbow saturation of graphs
    Girao, Antonio
    Lewis, David
    Popielarz, Kamil
    JOURNAL OF GRAPH THEORY, 2020, 94 (03) : 421 - 444
  • [22] RAINBOW CONNECTION IN GRAPHS
    Chartrand, Gary
    Johns, Garry L.
    McKeon, Kathleen A.
    Zhang, Ping
    MATHEMATICA BOHEMICA, 2008, 133 (01): : 85 - 98
  • [23] On Coloring Catalan Number Distance Graphs and Interference Graphs
    Yegnanarayanan, Venkataraman
    Yegnanarayanan, Gayathri Narayana
    Balas, Marius M.
    SYMMETRY-BASEL, 2018, 10 (10):
  • [24] RAINBOW DISCONNECTION IN GRAPHS
    Chartrand, Gary
    Devereaux, Stephen
    Haynes, Teresa W.
    Hedetniemi, Stephen T.
    Zhang, Ping
    DISCUSSIONES MATHEMATICAE GRAPH THEORY, 2018, 38 (04) : 1007 - 1021
  • [25] Max-Coloring and Online Coloring with Bandwidths on Interval Graphs
    Pemmaraju, Sriram V.
    Raman, Rajiv
    Varadarajan, Kasturi
    ACM TRANSACTIONS ON ALGORITHMS, 2011, 7 (03)
  • [26] COMPLETE CHARACTERIZATION OF THE BIDEGREED SPLIT GRAPHS WITH THREE OR FOUR DISTINCT Aα-EIGENVALUES
    Sun, Wanting
    Li, Shuchao
    Li, Xuechao
    ROCKY MOUNTAIN JOURNAL OF MATHEMATICS, 2023, 53 (05) : 1571 - 1585
  • [27] The Overfull Conjecture on split-comparability and split-interval graphs
    da Soledade Gonzaga, Luis Gustavo
    de Sousa Cruz, Jadder Bismarck
    de Almeida, Sheila Morais
    da Silva, Candida Nunes
    DISCRETE APPLIED MATHEMATICS, 2023, 340 : 228 - 238
  • [28] Legally (Δ+2)-Coloring Bipartite Outerplanar Graphs in Cubic Time
    Huang, Danjun
    Lih, Ko-Wei
    Wang, Weifan
    COMBINATORIAL OPTIMIZATION AND APPLICATIONS, (COCOA 2015), 2015, 9486 : 617 - 632
  • [29] Randomly Coloring Constant Degree Graphs
    Dyer, Martin
    Frieze, Alan
    Hayes, Thomas P.
    Vigoda, Eric
    RANDOM STRUCTURES & ALGORITHMS, 2013, 43 (02) : 181 - 200
  • [30] The toughness of split graphs
    Woeginger, GJ
    DISCRETE MATHEMATICS, 1998, 190 (1-3) : 295 - 297
12345