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 条
  • [1] Coloring (4K1,C4,C6)-free graphs
    Penev, Irena
    DISCRETE MATHEMATICS, 2023, 346 (11)
  • [2] On Coloring a Class of Claw-free Graphs
    Dai, Yingjun
    Foley, Angele M.
    Hoang, Chinh T.
    ELECTRONIC NOTES IN THEORETICAL COMPUTER SCIENCE, 2019, 346 : 369 - 377
  • [3] Vertex coloring (4K1, hole-twin, 5-wheel)-free graphs
    Dai, Yingjun
    Foley, Angele M.
    Hoang, Chinh T.
    THEORETICAL COMPUTER SCIENCE, 2022, 914 : 14 - 22
  • [4] On coloring a class of claw-free and hole-twin-free graphs
    Dai, Yingjun
    Foley, Angele M.
    Hoang, Chinh T.
    DISCRETE APPLIED MATHEMATICS, 2022, 323 : 162 - 170
  • [5] Coloring the cliques of line graphs
    Bacso, Gabor
    Ryjacek, Zdenek
    Tuza, Zsolt
    DISCRETE MATHEMATICS, 2017, 340 (11) : 2641 - 2649
  • [6] A Note on Coloring (4K1, C4, C6)-Free Graphs with a C7
    Koutecky, Martin
    GRAPHS AND COMBINATORICS, 2022, 38 (05)
  • [7] An algorithm for 12-[5]coloring of triangle-free hexagonal graphs
    Zerovnik, J
    ITI 2005: PROCEEDINGS OF THE 27TH INTERNATIONAL CONFERENCE ON INFORMATION TECHNOLOGY INTERFACES, 2005, : 673 - 678
  • [8] An On-line Competitive Algorithm for Coloring Bipartite Graphs Without Long Induced Paths
    Micek, Piotr
    Wiechert, Veit
    ALGORITHMICA, 2017, 77 (04) : 1060 - 1070
  • [9] An On-line Competitive Algorithm for Coloring Bipartite Graphs Without Long Induced Paths
    Piotr Micek
    Veit Wiechert
    Algorithmica, 2017, 77 : 1060 - 1070
  • [10] 4-coloring H-free graphs when H is small
    Golovach, Petr A.
    Paulusma, Daniel
    Song, Jian
    DISCRETE APPLIED MATHEMATICS, 2013, 161 (1-2) : 140 - 150
12345