论文标题
诱导的奇数周期填料数，独立集和色数
Induced odd cycle packing number, independent sets, and chromatic number
论文作者
论文摘要
图形$ g $的感应奇数循环数字$ iocp（g）$是最大整数$ k $，因此$ g $包含由$ k $ pairwise pertex-disexExExExExexexexhincles奇数循环组成的诱导子图。 Bonamy等人的动机是由应用到几何图的应用，〜\ cite {indoc}证明了有界诱导的奇数循环填料数，有界的VC维度和线性独立数的图形为独立数的随机eptas允许。 We show that the assumption of bounded VC dimension is not necessary, exhibiting a randomized algorithm that for any integers $k\ge 0$ and $t\ge 1$ and any $n$-vertex graph $G$ of induced odd cycle packing number at most $k$ returns in time $O_{k,t}(n^{k+4})$ an independent set of $G$ whose size is at least $α（g） - n/t $具有很高的可能性。此外，我们为具有有限的奇数周期填料编号的图表提供了$χ$结合的结果，并使用它们为独立数设计QPTA，仅假设有界的诱发奇数循环填料编号。
The induced odd cycle packing number $iocp(G)$ of a graph $G$ is the maximum integer $k$ such that $G$ contains an induced subgraph consisting of $k$ pairwise vertex-disjoint odd cycles. Motivated by applications to geometric graphs, Bonamy et al.~\cite{indoc} proved that graphs of bounded induced odd cycle packing number, bounded VC dimension, and linear independence number admit a randomized EPTAS for the independence number. We show that the assumption of bounded VC dimension is not necessary, exhibiting a randomized algorithm that for any integers $k\ge 0$ and $t\ge 1$ and any $n$-vertex graph $G$ of induced odd cycle packing number at most $k$ returns in time $O_{k,t}(n^{k+4})$ an independent set of $G$ whose size is at least $α(G)-n/t$ with high probability. In addition, we present $χ$-boundedness results for graphs with bounded odd cycle packing number, and use them to design a QPTAS for the independence number only assuming bounded induced odd cycle packing number.
