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 条
  • [1] Tree-coloring problems of bounded treewidth graphs
    Bi Li
    Xin Zhang
    Journal of Combinatorial Optimization, 2020, 39 : 156 - 169
  • [2] Tree-coloring problems of bounded treewidth graphs
    Li, Bi
    Zhang, Xin
    JOURNAL OF COMBINATORIAL OPTIMIZATION, 2020, 39 (01) : 156 - 169
  • [3] Channel assignment on graphs of bounded treewidth
    McDiarmid, C
    Reed, B
    DISCRETE MATHEMATICS, 2003, 273 (1-3) : 183 - 192
  • [4] Complexity and exact algorithms for vertex multicut in interval and bounded treewidth graphs
    Guo, Jiong
    Hueffner, Falk
    Kenar, Erhan
    Niedermeier, Rolf
    Uhlmann, Johannes
    EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2008, 186 (02) : 542 - 553
  • [5] The challenges of unbounded treewidth in parameterised subgraph counting problems
    Meeks, Kitty
    DISCRETE APPLIED MATHEMATICS, 2016, 198 : 170 - 194
  • [6] Combinatorial optimization on graphs of bounded treewidth
    Bodlaender, Hans L.
    Koster, Arie M. C. A.
    COMPUTER JOURNAL, 2008, 51 (03) : 255 - 269
  • [7] An algorithm for the Tutte polynomials of graphs of bounded treewidth
    Andrzejak, A
    DISCRETE MATHEMATICS, 1998, 190 (1-3) : 39 - 54
  • [8] Locally constrained homomorphisms on graphs of bounded treewidth and bounded degree
    Chaplick, Steven
    Fiala, Jiri
    van't Hof, Pim
    Paulusma, Daniel
    Tesar, Marek
    THEORETICAL COMPUTER SCIENCE, 2015, 590 : 86 - 95
  • [9] THE SIZE RAMSEY NUMBER OF GRAPHS WITH BOUNDED TREEWIDTH
    Kamcev, Nina
    Liebenau, Anita
    Wood, David R.
    Yepremyan, Liana
    SIAM JOURNAL ON DISCRETE MATHEMATICS, 2021, 35 (01) : 281 - 293
  • [10] On the Parameterised Complexity of String Morphism Problems
    Fernau, Henning
    Schmid, Markus L.
    Villanger, Yngve
    THEORY OF COMPUTING SYSTEMS, 2016, 59 (01) : 24 - 51
12345