Aravind, N R and Kalyanasundaram, Subrahmanyam and Kare, Anjeneya Swami
(2019)
HFree Coloring on Graphs with Bounded TreeWidth.
In: 5th International Conference on Algorithms and Discrete Applied Mathematics, CALDAM, 1416 February 2019, Kharagpur, India.
Full text not available from this repository.
(
Request a copy)
Abstract
Let H be a fixed undirected graph. A vertex coloring of an undirected input graph G is said to be an HFree Coloring if none of the color classes contain H as an induced subgraph. The HFree Chromatic Number of G is the minimum number of colors required for an HFree Coloring of G. This problem is NPcomplete and is expressible in monadic second order logic (MSOL). The MSOL formulation, together with Courcelle’s theorem implies linear time solvability on graphs with bounded treewidth. This approach yields an algorithm with running time f(∥ φ∥, t) · n, where ∥φ∥ is the length of the MSOL formula, t is the treewidth of the graph and n is the number of vertices of the graph. The dependency of f(∥φ∥, t) on ∥φ∥ can be as bad as a tower of exponentials. In this paper, we provide an explicit combinatorial FPT algorithm to compute the HFree Chromatic Number of a given graph G, parameterized by the treewidth of G. The techniques are also used to provide an FPT algorithm when H is forbidden as a subgraph (not necessarily induced) in the color classes of G.
[error in script]
Actions (login required)

View Item 