A coloring algorithm for 4K1-free line graphs

被引：5
|
作者：
Fraser, Dallas J. [1 ]
Hamel, Angele M. [1 ]
Hoang, Chinh T. [1 ]
Maffray, Frederic [2 ]
机构：
[1] Wilfrid Laurier Univ, Dept Phys & Comp Sci, Waterloo, ON, Canada
[2] Univ Grenoble Alpes, CNRS, Lab G SCOP, Grenoble, France
来源：
DISCRETE APPLIED MATHEMATICS | 2018年 / 234卷
基金：
加拿大自然科学与工程研究理事会;
关键词：
Graph coloring; Claw; K-5 \ e; Line-graph;
D O I：
10.1016/j.dam.2017.06.006
中图分类号：
O29 [应用数学];
学科分类号：
070104 ;
摘要：
Given a family F of graphs, let Free(F) be the class of graphs that do not contain any member of as an induced subgraph. When F is a set of four-vertex graphs the complexity of the vertex coloring problem in Free(F) is known, with three exceptions: F = {claw, 4K(1)}, = {claw, 4K(1), co-diamond}, and F = {C-4, 4K(1)}. In this paper, we study the coloring problem for Free(claw, 4K(1)). We solve the vertex coloring problem for a subclass of Free(claw, 4K(1)) which contains the class of 4K(1)-free line graphs. (C) 2017 Elsevier B.V. All rights reserved.
引用
收藏
页码：76 / 85
页数：10
相关论文
共 50 条
  • [41] On the Minimum Sum Coloring of P 4-Sparse Graphs
    Bonomo, Flavia
    Valencia-Pabon, Mario
    GRAPHS AND COMBINATORICS, 2014, 30 (02) : 303 - 314
  • [42] On the Minimum Sum Coloring of P4-Sparse Graphs
    Flavia Bonomo
    Mario Valencia-Pabon
    Graphs and Combinatorics, 2014, 30 : 303 - 314
  • [43] A note on the network coloring game: A randomized distributed (?+1)-coloring algorithm
    Fryganiotis, Nikolaos
    Papavassiliou, Symeon
    Pelekis, Christos
    INFORMATION PROCESSING LETTERS, 2023, 182
  • [44] Recognizing hinge-free line graphs and total graphs
    Chang, JM
    Ho, CW
    TAIWANESE JOURNAL OF MATHEMATICS, 2001, 5 (04): : 789 - 801
  • [45] Hamilton connectivity of line graphs and claw-free graphs
    Hu, ZQ
    Tian, F
    Wei, B
    JOURNAL OF GRAPH THEORY, 2005, 50 (02) : 130 - 141
  • [46] (2P2,K4)-FREE GRAPHS ARE 4-COLORABLE
    Gaspers, Serge
    Huang, Shenwei
    SIAM JOURNAL ON DISCRETE MATHEMATICS, 2019, 33 (02) : 1095 - 1120
  • [47] Three-Coloring Triangle-Free Planar Graphs in Linear Time
    Dvorak, Zdenek
    Kawarabayashi, Ken-Ichi
    Thomas, Robin
    ACM TRANSACTIONS ON ALGORITHMS, 2011, 7 (04)
  • [48] Coloring (P5,gem) $({P}_{5},\text{gem})$-free graphs with Δ -1 ${\rm{\Delta }}-1$ colors
    Cranston, Daniel W.
    Lafayette, Hudson
    Rabern, Landon
    JOURNAL OF GRAPH THEORY, 2022, 101 (04) : 633 - 642
  • [49] k-tree connectivity of line graphs
    Li, Shasha
    DISCRETE MATHEMATICS, 2021, 344 (12)
  • [50] L(2,1)-Labeling of Kneser graphs and coloring squares of Kneser graphs
    Shao, Zhendong
    Averbakh, Igor
    Solis-Oba, Roberto
    DISCRETE APPLIED MATHEMATICS, 2017, 221 : 106 - 114
12345