Description
EGERVÁRY SZEMINÁRIUM
Absztrakt:
A properly colored spanning tree in an edge-colored graph is a spanning tree in which every two adjacent edges have distinct colors. A weakly properly colored spanning tree T with fixed root r is a spanning tree in which every path in T, from r to any leaf, is a properly colored path. In this talk, We show that it is NP-complete to determine whether 2-edge-colored planar graph with maximum degree four contains a properly colored spanning tree, and it is W[1]-hard to decide whether an edge-colored graph contains a weakly properly colored spanning tree when parameterized by the treewidth. On the positive side, we show that these problems are fixed-parameter tractable when parameterized by combining the treewidth and the number of colors.