A weaker version of Lovasz' path removal conjecture

Autor(es)

Kawarabayashi, Ken-ichi ^[1] ; Lee, Orlando ^[2] ; Reed, Bruce ^[3] ; Wollan, Paul ^[4]

Afiliação do(s) autor(es)

^[1] Tohoku Univ. GSIS

^[2] Univ Estadual Campinas. Campinas

^[3] McGill Univ. Canada Res Chair Graph Theory

^[4] Univ Waterloo. Waterloo

• Tipo de documento: Artigo Científico
• Fonte: JOURNAL OF COMBINATORIAL THEORY SERIES B; v. 98, n. 5, p. 972-979, SEP 2008.
• Citações Web of Science: 7

Resumo

We prove there exists a function f (k) such that for every f (k)-connected graph G and for every edge e epsilon E(G), there exists an induced cycle C containing e such that G - E(C) is k-connected. This proves a weakening of a conjecture of Lovasz due to Kriesell. (C) 2008 Elsevier Inc. All rights reserved. (AU)

• Processo FAPESP: 03/09925-5 - Fundamentos da ciência da computação: algoritmos combinatórios e estruturas discretas
• Beneficiário: Yoshiharu Kohayakawa
• Modalidade de apoio: Auxílio à Pesquisa - Programa PRONEX - Temático