Induced odd cycle packing number, independent sets, and chromatic number

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F23%3A10473808" target="_blank" >RIV/00216208:11320/23:10473808 - isvavai.cz</a>

Výsledek na webu

<a href="https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=JiDIp0EpWF" target="_blank" >https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=JiDIp0EpWF</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1002/jgt.22932" target="_blank" >10.1002/jgt.22932</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Induced odd cycle packing number, independent sets, and chromatic number

Popis výsledku v původním jazyce

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. proved that graphs of bounded induced odd cycle packing number, bounded Vapnik-Chervonenkis (VC) dimension, and linear independence number admit a randomized efficient polynomial-time approximation scheme 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 &gt;= 0 and t &gt;= 1 and any n-vertex graph G of induced odd cycle packing number at most k returns in time O-k,O-t(n(k+4)) an independent set of G whose size is at least alpha(G)-n/t (G)-n with high probability. In addition, we present chi-boundedness results for graphs with bounded odd cycle packing number, and use them to design a quasipolynomial-time approximation scheme for the independence number only assuming bounded induced odd cycle packing number.

Název v anglickém jazyce

Induced odd cycle packing number, independent sets, and chromatic number

Popis výsledku anglicky

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. proved that graphs of bounded induced odd cycle packing number, bounded Vapnik-Chervonenkis (VC) dimension, and linear independence number admit a randomized efficient polynomial-time approximation scheme 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 &gt;= 0 and t &gt;= 1 and any n-vertex graph G of induced odd cycle packing number at most k returns in time O-k,O-t(n(k+4)) an independent set of G whose size is at least alpha(G)-n/t (G)-n with high probability. In addition, we present chi-boundedness results for graphs with bounded odd cycle packing number, and use them to design a quasipolynomial-time approximation scheme for the independence number only assuming bounded induced odd cycle packing number.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

<a href="/cs/project/GA17-04611S" target="_blank" >GA17-04611S: Ramseyovské aspekty barvení grafů</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2023

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

Journal of Graph Theory

ISSN

0364-9024

e-ISSN

1097-0118

Svazek periodika

103

Číslo periodika v rámci svazku

3

Stát vydavatele periodika

US - Spojené státy americké

Počet stran výsledku

15

Strana od-do

502-516

Kód UT WoS článku

000939501100001

EID výsledku v databázi Scopus

2-s2.0-85148458968