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 条
  • [11] An ant-based algorithm for coloring graphs
    Bui, Thang N.
    Nguyen, ThanhVu H.
    Patel, Chirag M.
    Phan, Kim-Anh T.
    DISCRETE APPLIED MATHEMATICS, 2008, 156 (02) : 190 - 200
  • [12] On line graphs of subcubic triangle-free graphs
    Munaro, Andrea
    DISCRETE MATHEMATICS, 2017, 340 (06) : 1210 - 1226
  • [13] Dynamic F-free Coloring of Graphs
    Piotr Borowiecki
    Elżbieta Sidorowicz
    Graphs and Combinatorics, 2018, 34 : 457 - 475
  • [14] Dynamic F-free Coloring of Graphs
    Borowiecki, Piotr
    Sidorowicz, Elzbieta
    GRAPHS AND COMBINATORICS, 2018, 34 (03) : 457 - 475
  • [15] COLORING BULL-FREE PERFECT GRAPHS
    Penev, Irena
    SIAM JOURNAL ON DISCRETE MATHEMATICS, 2012, 26 (03) : 1281 - 1309
  • [16] Conflict-free coloring on subclasses of perfect graphs and bipartite graphs
    Bhyravarapu, Sriram
    Kalyanasundaram, Subrahmanyam
    Mathew, Rogers
    THEORETICAL COMPUTER SCIENCE, 2025, 1031
  • [17] Rooted Complete Minors in Line Graphs with a Kempe Coloring
    Kriesell, Matthias
    Mohr, Samuel
    GRAPHS AND COMBINATORICS, 2019, 35 (02) : 551 - 557
  • [18] Rooted Complete Minors in Line Graphs with a Kempe Coloring
    Matthias Kriesell
    Samuel Mohr
    Graphs and Combinatorics, 2019, 35 : 551 - 557
  • [19] On the Structure of Graphs Without Claw, 4K1 and co-R
    Abuadas, Tala
    Hoang, Chinh T.
    GRAPHS AND COMBINATORICS, 2022, 38 (04)
  • [20] On approximation algorithms for coloring k-colorable graphs
    Xie, XZ
    Ono, T
    Hirata, T
    IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES, 2003, E86A (05): : 1046 - 1051
12345