论文标题
在遗传图课中找到大型$ h $ - 可油的子图
Finding large $H$-colorable subgraphs in hereditary graph classes
论文作者
论文摘要
我们研究\ textsc {max partial $ h $ -o-coloring}问题：给定图形$ g $，找到最大的$ g $ $ g $的子图，该子$ G $将同构为$ h $，其中$ h $是无循环的固定图案图。请注意，当$ h $是$ k $顶点上的完整图时，问题就会减少到找到最大的$ k $ - 颜色的子图，对于$ k = 2 $，它是等效的（通过补充）到\ textsc {奇数周期横向}。 我们证明，对于每个固定的图案图$ h $无循环，\ textsc {max partial $ h $ - 彩色}可以解决： $ \ bullet $ in $ \ {p_5，f \} $ - 多项式时间中的免费图形，每当$ f $是阈值图； $ \ bullet $ in $ \ {p_5，\ textrm {bull} \} $ - 多项式时间中的免费图形； $ \ bullet $ in $ p_5 $ -free graphs in Time $ n^{\ Mathcal {o}（ω（g））} $; $ \ bullet $ in $ \ {p_6，\ textrm {1-subdivided claw} \} $ - 时间$ n^{\ Mathcal {o}（ω（g）^3）} $。 在这里，$ n $是输入图$ g $的顶点，$ω（g）$是〜$ g $中一个集团的最大大小。 Furthermore, combining the mentioned algorithms for $P_5$-free and for $\{P_6,\textrm{1-subdivided claw}\}$-free graphs with a simple branching procedure, we obtain subexponential-time algorithms for \textsc{Max Partial $H$-Coloring} in these classes of graphs.最后，我们表明，即使是\ textsc {max partial $ h $ - 颜色}的受限制变体，如果我们允许在$ h $上进行循环，则在被考虑的子类中，在被考虑的子类中很难。
We study the \textsc{Max Partial $H$-Coloring} problem: given a graph $G$, find the largest induced subgraph of $G$ that admits a homomorphism into $H$, where $H$ is a fixed pattern graph without loops. Note that when $H$ is a complete graph on $k$ vertices, the problem reduces to finding the largest induced $k$-colorable subgraph, which for $k=2$ is equivalent (by complementation) to \textsc{Odd Cycle Transversal}. We prove that for every fixed pattern graph $H$ without loops, \textsc{Max Partial $H$-Coloring} can be solved: $\bullet$ in $\{P_5,F\}$-free graphs in polynomial time, whenever $F$ is a threshold graph; $\bullet$ in $\{P_5,\textrm{bull}\}$-free graphs in polynomial time; $\bullet$ in $P_5$-free graphs in time $n^{\mathcal{O}(ω(G))}$; $\bullet$ in $\{P_6,\textrm{1-subdivided claw}\}$-free graphs in time $n^{\mathcal{O}(ω(G)^3)}$. Here, $n$ is the number of vertices of the input graph $G$ and $ω(G)$ is the maximum size of a clique in~$G$. Furthermore, combining the mentioned algorithms for $P_5$-free and for $\{P_6,\textrm{1-subdivided claw}\}$-free graphs with a simple branching procedure, we obtain subexponential-time algorithms for \textsc{Max Partial $H$-Coloring} in these classes of graphs. Finally, we show that even a restricted variant of \textsc{Max Partial $H$-Coloring} is $\mathsf{NP}$-hard in the considered subclasses of $P_5$-free graphs, if we allow loops on $H$.
