On Structural Parameterizations of Load Coloring

• Published in: arXiv.org 2020-10
• Main Author: I Vinod Reddy
• Format: Article
• Language: English
• Subjects: Apexes; Clusters; Coloring; Graph theory; Graphs; Kernels; Parameters
• ISSN: 2331-8422

Given a graph \(G\) and a positive integer \(k\), the 2-Load coloring problem is to check whether there is a \(2\)-coloring \(f:V(G) \rightarrow \{r,b\}\) of \(G\) such that for every \(i \in \{r,b\}\), there are at least \(k\) edges with both end vertices colored \(i\). It is known that the problem is NP-complete even on special classes of graphs like regular graphs. Gutin and Jones (Inf Process Lett 114:446-449, 2014) showed that the problem is fixed-parameter tractable by giving a kernel with at most \(7k\) vertices. Barbero et al. (Algorithmica 79:211-229, 2017) obtained a kernel with less than \(4k\) vertices and \(O(k)\) edges, improving the earlier result. In this paper, we study the parameterized complexity of the problem with respect to structural graph parameters. We show that \lcp{} cannot be solved in time \(f(w)n^{o(w)}\), unless ETH fails and it can be solved in time \(n^{O(w)}\), where \(n\) is the size of the input graph, \(w\) is the clique-width of the graph and \(f\) is an arbitrary function of \(w\). Next, we consider the parameters distance to cluster graphs, distance to co-cluster graphs and distance to threshold graphs, which are weaker than the parameter clique-width and show that the problem is fixed-parameter tractable (FPT) with respect to these parameters. Finally, we show that \lcp{} is NP-complete even on bipartite graphs and split graphs.