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 条
  • [21] A SELF-STABILIZING ALGORITHM FOR COLORING PLANAR GRAPHS
    GHOSH, S
    KARAATA, MH
    DISTRIBUTED COMPUTING, 1993, 7 (01) : 55 - 59
  • [22] Clique-Coloring Claw-Free Graphs
    Liang, Zuosong
    Shan, Erfang
    Kang, Liying
    GRAPHS AND COMBINATORICS, 2016, 32 (04) : 1473 - 1488
  • [23] Clique-Coloring Claw-Free Graphs
    Zuosong Liang
    Erfang Shan
    Liying Kang
    Graphs and Combinatorics, 2016, 32 : 1473 - 1488
  • [24] Total Coloring of Claw-Free Planar Graphs
    Liang, Zuosong
    DISCUSSIONES MATHEMATICAE GRAPH THEORY, 2022, 42 (03) : 771 - 777
  • [25] Three-coloring triangle-free graphs on surfaces V. Coloring planar graphs with distant anomalies
    Dvorak, Zdenek
    Kral, Daniel
    Thomas, Robin
    JOURNAL OF COMBINATORIAL THEORY SERIES B, 2021, 150 : 244 - 269
  • [26] All 4-connected line graphs of claw free graphs are hamiltonian connected
    Kriesell, M
    JOURNAL OF COMBINATORIAL THEORY SERIES B, 2001, 82 (02) : 306 - 315
  • [27] Minimum sum set coloring of trees and line graphs of trees
    Bonomo, Flavia
    Duran, Guillermo
    Marenco, Javier
    Valencia-Pabon, Mario
    DISCRETE APPLIED MATHEMATICS, 2011, 159 (05) : 288 - 294
  • [28] Closure for {K1,4, K1,4 + e}-free graphs
    Ryjacek, Zdenek
    Vrana, Petr
    Wang, Shipeng
    JOURNAL OF COMBINATORIAL THEORY SERIES B, 2019, 134 : 239 - 263
  • [29] OBSTRUCTIONS FOR THREE-COLORING AND LIST THREE-COLORING H-FREE GRAPHS
    Chudnovsky, Maria
    Goedgebeur, Jan
    Schaudt, Oliver
    Zhong, Mingxian
    SIAM JOURNAL ON DISCRETE MATHEMATICS, 2020, 34 (01) : 431 - 469
  • [30] Three Complexity Results on Coloring Pk-Free Graphs
    Broersma, Hajo
    Fomin, Fedor V.
    Golovach, Petr A.
    Paulusma, Daniel
    COMBINATORIAL ALGORITHMS, 2009, 5874 : 95 - +
12345