- 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 : Thursday, November 15, 2018 - 3:43:15 PM

Long-term archiving on : Wednesday, May 31, 2017 - 4:44:43 PM

Contributor : Christophe Paul <>

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

Last modification on : Thursday, November 15, 2018 - 3:43:15 PM

Long-term archiving on : Wednesday, May 31, 2017 - 4:44:43 PM