Choosability on H-free graphs

被引：3
作者：
Golovach, Petr A. [1 ]
Heggernes, Pinar [1 ]
van't Hof, Pim [1 ]
Paulusma, Daniel [2 ]
机构：
[1] Univ Bergen, Dept Informat, N-5020 Bergen, Norway
[2] Univ Durham, Sch Engn & Comp Sci, Durham DH1 3HP, England
来源：
INFORMATION PROCESSING LETTERS | 2013年 / 113卷 / 04期
基金：
英国工程与自然科学研究理事会; 欧洲研究理事会;
关键词：
Computational complexity; Choosability; H-free graphs; Linear forest; CHOICE NUMBER; COLORING GRAPHS; NP-COMPLETENESS; PLANAR GRAPH; COMPLEXITY;
D O I：
10.1016/j.ipl.2012.12.003
中图分类号：
TP [自动化技术、计算机技术];
学科分类号：
0812 ;
摘要：
A graph is H-free if it has no induced subgraph isomorphic to H. We determine the computational complexity of the CHOOSABILITY problem restricted to H-free graphs for every graph H that does not belong to {K-1,K-3, P-1 + P-2, P-1 + P-3, P-4}. We also show that if H is a linear forest, then the problem is fixed-parameter tractable when parameterized by k. (C) 2012 Elsevier B.V. All rights reserved.
引用
收藏
页码：107 / 110
页数：4
相关论文
共 50 条
  • [31] On the Choosability of Claw-Free Perfect Graphs
    Sylvain Gravier
    Frédéric Maffray
    Lucas Pastor
    Graphs and Combinatorics, 2016, 32 : 2393 - 2413
  • [32] Choosability and edge choosability of planar graphs without intersecting triangles
    Wang, WF
    Lih, KW
    SIAM JOURNAL ON DISCRETE MATHEMATICS, 2002, 15 (04) : 538 - 545
  • [33] Minimum choosability of planar graphs
    Huijuan Wang
    Bin Liu
    Ling Gai
    Hongwei Du
    Jianliang Wu
    Journal of Combinatorial Optimization, 2018, 36 : 13 - 22
  • [34] Choosability and edge choosability of planar graphs without five cycles
    Wang, WF
    Lih, KW
    APPLIED MATHEMATICS LETTERS, 2002, 15 (05) : 561 - 565
  • [35] 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
  • [36] LOWER BOUNDS FOR MAX-CUT IN H-FREE GRAPHS VIA SEMIDEFINITE PROGRAMMING
    Carlson, Charles
    Kolla, Alexandra
    Li, Ray
    Mani, Nitya
    Sudakov, Benny
    Trevisan, Luca
    SIAM JOURNAL ON DISCRETE MATHEMATICS, 2021, 35 (03) : 1557 - 1568
  • [37] Minimum choosability of planar graphs
    Wang, Huijuan
    Liu, Bin
    Gai, Ling
    Du, Hongwei
    Wu, Jianliang
    JOURNAL OF COMBINATORIAL OPTIMIZATION, 2018, 36 (01) : 13 - 22
  • [38] On 3-choosability of triangle-free plane graphs
    Wang YingQian
    Zhang QiJun
    SCIENCE CHINA-MATHEMATICS, 2011, 54 (06) : 1287 - 1298
  • [39] On the acyclic choosability of graphs
    Montassier, M
    Ochem, P
    Raspaud, A
    JOURNAL OF GRAPH THEORY, 2006, 51 (04) : 281 - 300
  • [40] On 3-choosability of triangle-free plane graphs
    YingQian Wang
    QiJun Zhang
    Science China Mathematics, 2011, 54
12345