$H$-Free Coloring on Graphs with Bounded Tree-Width

Abstract

Let $H$ be a fixed undirected graph. A vertex coloring of an undirected input graph $G$ is said to be an $H$-Free Coloring if none of the color classes contain $H$ as an induced subgraph. The $H$-Free Chromatic Number of $G$ is the minimum number of colors required for an $H$-Free Coloring of $G$. This problem is NP-complete 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 tree-width. This approach yields an algorithm with running time $f(\lVert \varphi \rVert, t)\cdot n$, where $\lVert \varphi \rVert$ is the length of the MSOL formula, $t$ is the tree-width of the graph and $n$ is the number of vertices of the graph. The dependency of $f(\lVert \varphi \rVert, t)$ on $\lVert \varphi \rVert$ can be as bad as a tower of exponentials.

In this paper, we provide an explicit combinatorial FPT algorithm to compute the $H$-Free Chromatic Number of a given graph $G$, parameterized by the tree-width 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$.

Publication
Proceedings of the 5th International Conference on Algorithms and Discrete Applied Mathematics - CALDAM 2019, Kharagpur, India.

Related