MIN-MAX RELATIONS FOR ODD CYCLES IN PLANAR GRAPHS

KRÁĽ, Daniel; JS SERENI a L STACHO. MIN-MAX RELATIONS FOR ODD CYCLES IN PLANAR GRAPHS. SIAM Journal on Discrete Mathematics. Philadelphia: SIAM, 2012, roč. 26, č. 3, s. 884-895. ISSN 0895-4801. Dostupné z: https://doi.org/10.1137/110845835.

Základní údaje

Originální název

MIN-MAX RELATIONS FOR ODD CYCLES IN PLANAR GRAPHS

Autoři

KRÁĽ, Daniel; JS SERENI a L STACHO

Vydání

SIAM Journal on Discrete Mathematics, Philadelphia, SIAM, 2012, 0895-4801

---

Další údaje

Jazyk

angličtina

Typ výsledku

Článek v odborném periodiku

Utajení

není předmětem státního či obchodního tajemství

Impakt faktor

Impact factor: 0.662

Označené pro přenos do RIV

Ne

DOI

https://doi.org/10.1137/110845835

UT WoS

000309976400002

Klíčová slova anglicky

Erdos-Posa property; planar graphs; odd cycle transversals; T-joins

---

Anotace

V originále

Let nu(G) be the maximum number of vertex-disjoint odd cycles of a graph G and tau(G) the minimum number of vertices whose removal makes G bipartite. We show that tau(G) <= 6 nu(G) if G is planar. This improves the previous bound tau(G) <= 10 nu(G) by Fiorini et al. [Math. Program. Ser. B, 110 (2007), pp. 71-91].