Equitable Clique-Coloring in Claw-Free Graphs with Maximum Degree at Most 4

被引:1
作者
Liang, Zuosong [1 ]
Dong, Yanxia [2 ]
Zhao, Yancai [3 ]
Xing, Huiyu [1 ]
机构
[1] Qufu Normal Univ, Sch Management, Rizhao 276800, Peoples R China
[2] Shanghai Univ Int Business & Econ, Sch Stat & Informat, Shanghai 201620, Peoples R China
[3] Wuxi City Coll Vocat Technol, Wuxi 214153, Jiangsu, Peoples R China
关键词
Equitable clique-coloring; Claw-free graph; Linear time algorithm; TRANSVERSAL SETS; COMPLEXITY;
D O I
10.1007/s00373-020-02253-x
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
A clique of a graph G is a set of pairwise adjacent vertices of G. A clique-coloring of G is an assignment of colors to the vertices of G in such a way that no inclusion-wise maximal clique of size at least two of G is monochromatic. An equitable clique-coloring of G is a clique-coloring such that any two color classes differ in size by at most one. Bacso and Tuza proved that connected claw-free graphs with maximum degree at most four, other than chordless odd cycles of order greater than three, are 2-clique-colorable and a 2-clique-coloring can be found in O(n(2)) Bacso and Tuza (Discrete Math Theor Comput Sci 11(2):15-24, 2009). In this paper we prove that every connected claw-free graph with maximum degree at most four, not a chordless odd cycle of order greater than three, has an equitable 2-clique-coloring. In addition we improve the algorithm described in the paper mentioned by giving an equitable 2-clique-coloring in linear time for this class of graphs.
引用
收藏
页码:445 / 454
页数:10
相关论文
共 22 条
  • [1] Coloring the maximal cliques of graphs
    Bacsó, G
    Gravier, S
    Gyárfás, A
    Preissmann, M
    Sebo, A
    [J]. SIAM JOURNAL ON DISCRETE MATHEMATICS, 2004, 17 (03) : 361 - 376
  • [2] Coloring the cliques of line graphs
    Bacso, Gabor
    Ryjacek, Zdenek
    Tuza, Zsolt
    [J]. DISCRETE MATHEMATICS, 2017, 340 (11) : 2641 - 2649
  • [3] Bacsó G, 2009, DISCRETE MATH THEOR, V11, P15
  • [4] EQUIPARTITE COLORINGS IN GRAPHS AND HYPERGRAPHS
    BERGE, C
    STERBOUL, F
    [J]. JOURNAL OF COMBINATORIAL THEORY SERIES B, 1977, 22 (02) : 97 - 113
  • [5] Perfect graphs of arbitrarily large clique-chromatic number
    Charbit, Pierre
    Penev, Irena
    Thomasse, Stephan
    Trotignon, Nicolas
    [J]. JOURNAL OF COMBINATORIAL THEORY SERIES B, 2016, 116 : 456 - 464
  • [6] EQUITABLE COLORING AND THE MAXIMUM DEGREE
    CHEN, BL
    LIH, KW
    WU, PL
    [J]. EUROPEAN JOURNAL OF COMBINATORICS, 1994, 15 (05) : 443 - 447
  • [7] Decomposing and Clique-Coloring (Diamond, Odd-Hole)-Free Graphs
    Chudnovsky, Maria
    Lo, Irene
    [J]. JOURNAL OF GRAPH THEORY, 2017, 86 (01) : 5 - 41
  • [8] Clique-coloring some classes of odd-hole-free graphs
    Defossez, David
    [J]. JOURNAL OF GRAPH THEORY, 2006, 53 (03) : 233 - 249
  • [9] Complexity of Clique-Coloring Odd-Hole-Free Graphs
    Defossez, David
    [J]. JOURNAL OF GRAPH THEORY, 2009, 62 (02) : 139 - 156
  • [10] Hajnal A., 1970, Combinatorial Theory and its Applications, P601