A graph is an opposition graph, respectively, a coalition graph, if it admits an acyclic orientation which puts the two end-edges of every chordless 4-vertex path in opposition, respectively, in the same direction. Opposition and coalition graphs have been introduced and investigated in connection to perfect graphs. Recognizing and characterizing opposition and coalition graphs are long-standing open problems. This paper gives characterizations for opposition graphs and coalition graphs on some restricted graph classes. Implicit in our arguments are polynomial time recognition algorithms for these graphs. We also give a good characterization for the so-called generalized opposition graphs.
The Gallai graph $\Gamma(G)$ of a graph $G$ has the edges of $G$ as its vertices and two distinct vertices $e$ and $f$ of $\Gamma(G)$ are adjacent in $\Gamma(G)$ if the edges $e$ and $f$ of $G$ are adjacent in $G$ but do not span a triangle in $G$. Clearly, $\Gamma(G)$ is a subgraph of the line graph of $G$. While line graphs can be recognized efficiently the complexity of recognizing Gallai graphs is unknown. In the present paper we characterize those graphs whose Gallai graphs are forests or trees, respectively.
A stable cutset in a graph $G$ is a set $S\subseteq V(G)$ such that vertices of $S$ are pairwise non-adjacent and such that $G-S$ is disconnected, i.e., it is both stable (or independent) set and a cutset (or separator). Unlike general cutsets, it is $NP$-complete to determine whether a given graph $G$ has any stable cutset. Recently, Rauch et al.\ [FCT 2023] gave a number of fixed-parameter tractable (FPT) algorithms, time $f(k)\cdot |V(G)|^c$, for Stable Cutset under a variety of parameters $k$ such as the size of a (given) dominating set, the size of an odd cycle transversal, or the deletion distance to $P_5$-free graphs. Earlier works imply FPT algorithms relative to clique-width and relative to solution size. We complement these findings by giving the first results on the existence of polynomial kernelizations for \stablecutset, i.e., efficient preprocessing algorithms that return an equivalent instance of size polynomial in the parameter value. Under the standard assumption that $NP\nsubseteq coNP/poly$, we show that no polynomial kernelization is possible relative to the deletion distance to a single path, generalizing deletion distance to various graph classes, nor by the size of a (given) dominating set. We also show that under the same assumption no polynomial kernelization is possible relative to solution size, i.e., given $(G,k)$ answering whether there is a stable cutset of size at most $k$. On the positive side, we show polynomial kernelizations for parameterization by modulators to a single clique, to a cluster or a co-cluster graph, and by twin cover.
'%3e%3cpath fill='%23012169' d='M0 0v30h60V0z'/%3e%3cpath stroke='%23fff' stroke-width='6' d='m0 0 60 30m0-30L0 30'/%3e%3cpath stroke='%23C8102E' stroke-width='4' d='m0 0 60 30m0-30L0 30' clip-path='url(%23b)'/%3e%3cpath stroke='%23fff' stroke-width='10' d='M30 0v30M0 15h60'/%3e%3cpath stroke='%23C8102E' stroke-width='6' d='M30 0v30M0 15h60'/%3e%3c/g%3e%3c/svg%3e)
