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 条
  • [41] On 3-choosability of triangle-free plane graphs
    WANG YingQian & ZHANG QiJun Department of Mathematics
    ScienceChina(Mathematics), 2011, 54 (06) : 1287 - 1298
  • [42] Girth and ?-choosability of graphs
    Gu, Yangyan
    Zhu, Xuding
    JOURNAL OF GRAPH THEORY, 2023, 103 (03) : 493 - 501
  • [43] On Polynomial Kernelization of H-FREE EDGE DELETION
    Aravind, N. R.
    Sandeep, R. B.
    Sivadasan, Naveen
    ALGORITHMICA, 2017, 79 (03) : 654 - 666
  • [44] On Polynomial Kernelization of H-FREE EDGE DELETION
    Aravind, N. R.
    Sandeep, R. B.
    Sivadasan, Naveen
    PARAMETERIZED AND EXACT COMPUTATION, IPEC 2014, 2014, 8894 : 28 - 38
  • [45] A note on the minimum number of choosability of planar graphs
    Huijuan Wang
    Lidong Wu
    Xin Zhang
    Weili Wu
    Bin Liu
    Journal of Combinatorial Optimization, 2016, 31 : 1013 - 1022
  • [46] Acyclic 4-choosability of planar graphs
    Chen, Min
    Raspaud, Andre
    Roussel, Nicolas
    Zhu, Xuding
    DISCRETE MATHEMATICS, 2011, 311 (01) : 92 - 101
  • [47] Improper choosability of graphs and maximum average degree
    Havet, F
    Sereni, JS
    JOURNAL OF GRAPH THEORY, 2006, 52 (03) : 181 - 199
  • [48] On (3, r)-Choosability of Some Planar Graphs
    Li, Heng
    Hou, Jianfeng
    Zhu, Hongguo
    BULLETIN OF THE MALAYSIAN MATHEMATICAL SCIENCES SOCIETY, 2022, 45 (02) : 851 - 867
  • [49] A note on 3-choosability of planar graphs
    Wang, Yingqian
    Lu, Huajing
    Chen, Ming
    INFORMATION PROCESSING LETTERS, 2008, 105 (05) : 206 - 211
  • [50] A note on the minimum number of choosability of planar graphs
    Wang, Huijuan
    Wu, Lidong
    Zhang, Xin
    Wu, Weili
    Liu, Bin
    JOURNAL OF COMBINATORIAL OPTIMIZATION, 2016, 31 (03) : 1013 - 1022
12345