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 条
  • [1] On Switching to H-Free Graphs
    Jelinkova, Eva
    Kratochvil, Jan
    JOURNAL OF GRAPH THEORY, 2014, 75 (04) : 387 - 405
  • [2] 4-coloring H-free graphs when H is small
    Golovach, Petr A.
    Paulusma, Daniel
    Song, Jian
    DISCRETE APPLIED MATHEMATICS, 2013, 161 (1-2) : 140 - 150
  • [3] Connected greedy coloring of H-free graphs
    Mota, Esdras
    Rocha, Leonardo
    Silva, Ana
    DISCRETE APPLIED MATHEMATICS, 2020, 284 (284) : 572 - 584
  • [4] Finding Matching Cuts in H-Free Graphs
    Lucke, Felicia
    Paulusma, Daniel
    Ries, Bernard
    ALGORITHMICA, 2023, 85 (10) : 3290 - 3322
  • [5] Contraction and deletion blockers for perfect graphs and H-free graphs
    Diner, Oznur Yasar
    Paulusma, Daniel
    Picouleau, Christophe
    Ries, Bernard
    THEORETICAL COMPUTER SCIENCE, 2018, 746 : 49 - 72
  • [6] Classifying k-edge colouring for H-free graphs
    Galby, Esther
    Lima, Paloma T.
    Paulusma, Daniel
    Ries, Bernard
    INFORMATION PROCESSING LETTERS, 2019, 146 : 39 - 43
  • [7] 4-Coloring H-Free Graphs When H Is Small
    Golovach, Petr A.
    Paulusma, Daniel
    Song, Jian
    SOFSEM 2012: THEORY AND PRACTICE OF COMPUTER SCIENCE, 2012, 7147 : 289 - 300
  • [8] Vertex Cover at Distance on H-Free Graphs
    Dallard, Clement
    Krbezlija, Mirza
    Milanic, Martin
    COMBINATORIAL ALGORITHMS, IWOCA 2021, 2021, 12757 : 237 - 251
  • [9] Exhaustive Generation of k-Critical H-Free Graphs
    Goedgebeur, Jan
    Schaudt, Oliver
    GRAPH-THEORETIC CONCEPTS IN COMPUTER SCIENCE, WG 2016, 2016, 9941 : 109 - 120
  • [10] Partitioning H-free graphs of bounded diameter
    Brause, Christoph
    Golovach, Petr
    Martin, Barnaby
    Paulusma, Daniel
    Smith, Siani
    THEORETICAL COMPUTER SCIENCE, 2022, 930 : 37 - 52
12345