// Workers AI · dad joke modeWhat did the Bisplit graph say? I'm split on the decision.

In graph theory, a bisplit graph is an undirected graph whose vertices can be partitioned into two subsets, one of which is an independent set and the other of which induces a complete bipartite graph (a biclique). They are defined analogously to split graphs, in which the vertices can be partitioned into an independent set and a complete subgraph. A weak bisplit graph generalizes the definition of a bisplit graph by allowing a partition into an independent set and a disjoint union of bicliques.

Computational complexity

The bisplit graphs may be recognized, and a bisplit partition constructed for them, in polynomial time. The algorithm starts by performing a breadth first search from an arbitrarily chosen vertex, and using it to find two adjacent vertices at the same distance as each other from the starting vertex, minimizing that distance. If they do not exist, the graph is bipartite and therefore bisplit. If they exist but do not form part of a triangle, then they are part of an odd induced cycle, which cannot exist in a bisplit graph, so the graph is not bisplit. In the remaining case, the algorithm has found a triangle, from which exactly one of the three vertices must belong to the independent set of a bisplit partition; the algorithm tests each of the resulting three choices.

For each choice of one triangle vertex $x$ as belonging to the independent set and the other two vertices $y$ and $z$ as belonging to the biclique, it remains to assign the remaining vertices to the independent set or to the biclique. This assignment has the following constraints:

• If a vertex $v$ is assigned to the independent set, $v$ must not be adjacent to $x$.
• If vertices $v$ and $w$ are both assigned to the independent set, they must not be adjacent to each other.
• If a vertex $v$ is assigned to the biclique, it must be adjacent to exactly one of $y$ or $z$.
• If vertices $v$ and $w$ are both assigned to the biclique, and both are adjacent to the same one of $y$ or $z$, they must not be adjacent to each other.
• If vertices $v$ and $w$ are both assigned to the biclique, and are not both adjacent to the same one of $y$ or $z$, they must be adjacent to each other.

Because each assignment has two choices (independent set or biclique) and each constraint involves at most two assignments, the problem of finding a valid assignment can be modeled as one of 2-satisfiability, and solved in time $O(n^{2})$.

The same algorithm can be generalized to finding weak bisplit graphs that have a bounded number of bisplit components, in polynomial time. However, recognizing weak bisplit graphs without a bound on the number of bisplit components is NP-complete.

Related graph classes

The bisplit graphs and weak bisplit graphs form subclasses of the graphs that can be 3-colored: one can use one color for the independent set of a bisplit graph and two more colors for the biclique or bicliques.

Every bisplit graph is a comparability graph, and hence also a perfect graph. This can be shown by constructing a transitive orientation of these graphs, an assignment of directions to edges that causes them to form a transitive relation. This may be done by directing each edge outward from the independent set, and consistently from one side of the biclique towards the other.

Every bipartite graph is bisplit, with a trivial biclique (one with no edges) on one side of its bipartition. A triangle-free graph is a bisplit graph if and only if it is bipartite.