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 条
  • [31] Conflict-Free Coloring: Graphs of Bounded Clique-Width and Intersection Graphs
    Bhyravarapu, Sriram
    Hartmann, Tim A.
    Hoang, Hung P.
    Kalyanasundaram, Subrahmanyam
    Reddy, I. Vinod
    ALGORITHMICA, 2024, 86 (07) : 2250 - 2288
  • [32] On the on-line coloring of unit interval graphs with proper interval representation
    Curbelo, Israel R.
    Malko, Hannah R.
    DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE, 2025, 27 (02)
  • [33] Three-coloring triangle-free graphs on surfaces IV. Bounding face sizes of 4-critical graphs
    Dvorak, Zdenek
    Kral', Daniel
    Thomas, Robin
    JOURNAL OF COMBINATORIAL THEORY SERIES B, 2021, 150 : 270 - 304
  • [34] Independent sets in {claw, K4}-free 4-regular graphs
    Kang, Liying
    Wang, Dingguo
    Shan, Erfang
    DISCRETE MATHEMATICS, 2014, 332 : 40 - 44
  • [35] An adaptive memory algorithm for the k-coloring problem
    Galinier, Philippe
    Hertz, Alain
    Zufferey, Nicolas
    DISCRETE APPLIED MATHEMATICS, 2008, 156 (02) : 267 - 279
  • [36] On the structure and clique-width of ( 4 K 1 , C 4 , C 6 , C 7 )-free graphs
    Penev, Irena
    JOURNAL OF GRAPH THEORY, 2022, 99 (03) : 435 - 460
  • [37] The κk-connectivity of line graphs
    Li, Hengzhe
    Lu, Yuanyuan
    Wu, Baoyindureng
    Wei, Ankang
    DISCRETE APPLIED MATHEMATICS, 2020, 285 (285) : 1 - 8
  • [38] Coloring k-colorable graphs using relatively small palettes
    Halperin, E
    Nathaniel, R
    Zwick, U
    JOURNAL OF ALGORITHMS-COGNITION INFORMATICS AND LOGIC, 2002, 45 (01): : 72 - 90
  • [39] Coloring graphs with no even hole ≥ 6: the triangle-free case
    Lagoutte, Aureie
    ELECTRONIC JOURNAL OF COMBINATORICS, 2017, 24 (03)
  • [40] Closing complexity gaps for coloring problems on H-free graphs
    Golovach, Petr A.
    Paulusma, Daniel
    Song, Jian
    INFORMATION AND COMPUTATION, 2014, 237 : 204 - 214
12345