# Is Maximum Independent Set polynomial-time solvable in $(p,1)$-colorable graphs for general $p$?

It is well-known that Maximum Independent Set (MIS) in bipartite graphs is polynomial-time solvable. What happens if we generalize the input graphs by replacing the vertices in one partite with cliques?

Formally, the graph $$G = (V, E)$$ is defined as follows. There is partition $$(A, B)$$ of $$V$$ such that $$G[A]$$ is an independent set and $$G[B]$$ is a cluster (the union of some disjoint cliques).

I wonder whether whether MIS in such graph classes is polynomial-time solvable.

It is NP-complete even when $$G[B]$$ is a disjoint union of cliques of size 2. This follows from the fact that subdiving every edge twice increases maximum independent set by exactly the number of edges, so MIS is NP-complete in twice subdivided graphs, but twice subdivided graphs can be partitioned into an independent set and a disjoint union of cliques of size 2.
No. A graph with $$n$$ vertices is trivially $$(n, 1)$$-colorable. So solving MIS in $$(p, 1)$$-colorable graphs in $$n^{O(1)}$$ time for non-constant $$p$$ implies we could solve MIS in $$n^{O(1)}$$ time for any graph.
• Sorry, I found a wrong definition. It is not a $(p,1)$-colorable graph. Commented Jun 16, 2023 at 17:11