  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.
