Conference papers

- it is W[1]-hard on multigraphs parameterized by the tree-cutwidth of the input multigraph;

- it is FPT parameterized by the star tree-cutwidth of the input graph, which is a slightly restricted version of tree-cutwidth. This result strictly generalizes the FPT result given in Gözüpek et al. [TCS 2016];

- it remains NP-hard on planar graphs even when restricted to instances with at most 6 colors and 0/1 symmetric costs, or when restricted to instances with at most 8 colors, maximum degree bounded by 4, and 0/1 symmetric costs.

Cited literature [20 references]

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01481360

Contributor : Christophe Paul <>

Submitted on : Thursday, March 2, 2017 - 2:57:34 PM

Last modification on : Tuesday, June 23, 2020 - 12:05:21 PM

Document(s) archivé(s) le : Wednesday, May 31, 2017 - 4:44:43 PM

Contributor : Christophe Paul <>

Submitted on : Thursday, March 2, 2017 - 2:57:34 PM

Last modification on : Tuesday, June 23, 2020 - 12:05:21 PM

Document(s) archivé(s) le : Wednesday, May 31, 2017 - 4:44:43 PM