Artículos de revistas
Removable paths and cycles with parity constraints
Journal Of Combinatorial Theory Series B. Academic Press Inc Elsevier Science, v. 106, n. 115, n. 133, 2014.
Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq)We consider the following problem. For every positive integer k there is a smallest integer f(k) such that for any two vertices s and t in a non-bipartite f(k)-connected graph G, there is an s-t path P in G with specified parity such that G - V(P) is k-connected. This conjecture is a variant of the well-known conjecture of Lovasz with the parity condition. Indeed, this conjecture is strictly stronger. Lovasz' conjecture is wide open for k >= 3. In this paper, we show that f(1) = 5 and 6 <= f(2) <= 8. We also consider a conjecture of Thomassen which says that there exists a function f(k) such that every f(k)-connected graph with an odd cycle contains an odd cycle C such that G - V(C) is k-connected. We show the following strengthening of Thomassen's conjecture for the case k = 2. Namely; let G be a 5-connected graph and s be a vertex in G such that G - s is not bipartite. Then there is an odd cycle C avoiding s such that G - V(C) is 2-connected. (C) 2014 Elsevier Inc. All rights reserved.106115133Japan Society for the Promotion of ScienceKayamori FoundationJST, ERATO, Kawarabayashi Large Graph ProjectConselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq)[Proc. 477692/2012-5]Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq)CNPq [Proc. 301310/2005-0, Proc. 472504/2007-0, Proc. 473867/2010-9][Proc. 477692/2012-5]