The parameterised complexity of list problems on graphs of bounded treewidth

被引：4
|
作者：
Meeks, Kitty [1 ,2 ]
Scott, Alexander [1 ]
机构：
[1] Univ Oxford, Math Inst, Radcliffe Observ Quarter, Andrew Wiles Bldg,Woodstock Rd, Oxford OX2 6GG, England
[2] Univ Glasgow, Sch Math & Stat, 15 Univ Gardens, Glasgow G12 8QW, Lanark, Scotland
来源：
INFORMATION AND COMPUTATION | 2016年 / 251卷
关键词：
Parameterised complexity; Bounded treewidth; Graph colouring; List colouring; Hamilton path; NP-COMPLETENESS; CHROMATIC INDEX; TOTAL COLORINGS; EDGE;
D O I：
10.1016/j.ic.2016.08.001
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
We consider the parameterised complexity of several list problems on graphs, with parameter treewidth or pathwidth. In particular, we show that LIST EDGE CHROMATIC NUMBER and LIST TOTAL CHROMATIC NUMBER are fixed parameter tractable, parameterised by treewidth, whereas LIST HAMILTON PATH is W[1]-hard, even parameterised by pathwidth. These results resolve two open questions of Fellows, Fomin, Lokshtanov, Rosamond, Saurabh, Szeider and Thomassen (2011). (C) 2016 Elsevier Inc. All rights reserved.
引用
收藏
页码：91 / 103
页数：13
相关论文
共 50 条
  • [21] List Edge-Coloring and Total Coloring in Graphs of Low Treewidth
    Bruhn, Henning
    Lang, Richard
    Stein, Maya
    JOURNAL OF GRAPH THEORY, 2016, 81 (03) : 272 - 282
  • [22] Complexity of domination, hamiltonicity and treewidth for tree convex bipartite graphs
    Chen, Hao
    Lei, Zihan
    Liu, Tian
    Tang, Ziyang
    Wang, Chaoyi
    Xu, Ke
    JOURNAL OF COMBINATORIAL OPTIMIZATION, 2016, 32 (01) : 95 - 110
  • [23] Approximation Schemes for Capacitated Vehicle Routing on Graphs of Bounded Treewidth, Bounded Doubling, or Highway Dimension
    Jayaprakash, Aditya
    Salavatipour, Mohammad R.
    ACM TRANSACTIONS ON ALGORITHMS, 2023, 19 (02)
  • [24] List packing number of bounded degree graphs
    Cambie, Stijn
    van Batenburg, Wouter Cames
    Davies, Ewan
    Kang, Ross J.
    COMBINATORICS PROBABILITY AND COMPUTING, 2024, 33 (06) : 807 - 828
  • [25] Approximation algorithms for optimization problems in graphs with superlogarithmic treewidth
    Czumaj, A
    Halldórsson, MM
    Lingas, A
    Nilsson, J
    INFORMATION PROCESSING LETTERS, 2005, 94 (02) : 49 - 53
  • [26] Complexity analysis of P3-convexity problems on bounded-degree and planar graphs
    Penso, Lucia Draque
    Protti, Fabio
    Rautenbach, Dieter
    Souza, Ueverton dos Santos
    THEORETICAL COMPUTER SCIENCE, 2015, 607 : 83 - 95
  • [27] Balancing Bounded Treewidth Circuits
    Maurice Jansen
    Jayalal Sarma
    Theory of Computing Systems, 2014, 54 : 318 - 336
  • [28] Balancing Bounded Treewidth Circuits
    Jansen, Maurice
    Sarma, Jayalal
    THEORY OF COMPUTING SYSTEMS, 2014, 54 (02) : 318 - 336
  • [29] Bi-arc graphs and the complexity of list homomorphisms
    Feder, T
    Hell, P
    Huang, J
    JOURNAL OF GRAPH THEORY, 2003, 42 (01) : 61 - 80
  • [30] The k-path coloring problem in graphs of bounded treewidth: An application in integrated circuit manufacturing
    Ait-Ferhat, Dehia
    Juliard, Vincent
    Stauffer, Gautier
    Torres, Juan Andres
    OPERATIONS RESEARCH LETTERS, 2020, 48 (05) : 652 - 657
12345