H-Free Coloring on Graphs with Bounded Tree-Width

Aravind, N R and Kalyanasundaram, Subrahmanyam and Kare, Anjeneya Swami (2019) H-Free Coloring on Graphs with Bounded Tree-Width. In: 5th International Conference on Algorithms and Discrete Applied Mathematics, CALDAM, 14-16 February 2019, Kharagpur, India.

Full text not available from this repository. (Request a copy)


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(∥ φ∥, t) · n, where ∥φ∥ 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(∥φ∥, t) on ∥φ∥ 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.

[error in script]
IITH Creators:
IITH CreatorsORCiD
Kalyanasundaram, SubrahmanyamUNSPECIFIED
Item Type: Conference or Workshop Item (Paper)
Subjects: Computer science
Divisions: Department of Computer Science & Engineering
Depositing User: Library Staff
Date Deposited: 16 Apr 2019 07:22
Last Modified: 16 Apr 2019 07:22
URI: http://raiith.iith.ac.in/id/eprint/4963
Publisher URL: http://doi.org/10.1007/978-3-030-11509-8_19
Related URLs:

Actions (login required)

View Item View Item
Statistics for RAIITH ePrint 4963 Statistics for this ePrint Item