2019/10/23 by I. Vinod Reddy, Reddy, I. Vinod
Computer Science · Neuroscience · #Advanced Graph Theory Research #Graph Labeling and Dimension Problems #Nuclear Receptors and Signaling
paper · pdf · doi:10.48550/arxiv.1910.10364
In this paper, we study several coloring problems on graphs from the viewpoint of parameterized complexity. We show that Precoloring Extension is fixed-parameter tractable (FPT) parameterized by distance to clique and Equitable Coloring is FPT parameterized by the distance to threshold graphs. We also study the List k-Coloring and show that the problem is NP-complete on split graphs and it is FPT parameterized by solution size on split graphs.