Removable paths and cycles with parity constraints

dc.creatorKawarabayashi, K
dc.creatorLee, O
dc.creatorReed, B
dc.date2014
dc.dateMAY
dc.date2014-07-30T18:23:08Z
dc.date2015-11-26T17:47:12Z
dc.date2014-07-30T18:23:08Z
dc.date2015-11-26T17:47:12Z
dc.date.accessioned2018-03-29T00:29:49Z
dc.date.available2018-03-29T00:29:49Z
dc.identifierJournal Of Combinatorial Theory Series B. Academic Press Inc Elsevier Science, v. 106, n. 115, n. 133, 2014.
dc.identifier0095-8956
dc.identifier1096-0902
dc.identifierWOS:000335427100006
dc.identifier10.1016/j.jctb.2014.01.005
dc.identifierhttp://www.repositorio.unicamp.br/jspui/handle/REPOSIP/70884
dc.identifierhttp://repositorio.unicamp.br/jspui/handle/REPOSIP/70884
dc.identifier.urihttp://repositorioslatinoamericanos.uchile.cl/handle/2250/1288713
dc.descriptionConselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq)
dc.descriptionWe 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.
dc.description106
dc.description115
dc.description133
dc.descriptionJapan Society for the Promotion of Science
dc.descriptionKayamori Foundation
dc.descriptionJST, ERATO, Kawarabayashi Large Graph Project
dc.descriptionConselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq)
dc.description[Proc. 477692/2012-5]
dc.descriptionConselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq)
dc.descriptionCNPq [Proc. 301310/2005-0, Proc. 472504/2007-0, Proc. 473867/2010-9]
dc.description[Proc. 477692/2012-5]
dc.languageen
dc.publisherAcademic Press Inc Elsevier Science
dc.publisherSan Diego
dc.publisherEUA
dc.relationJournal Of Combinatorial Theory Series B
dc.relationJ. Comb. Theory Ser. B
dc.rightsfechado
dc.rightshttp://www.elsevier.com/about/open-access/open-access-policies/article-posting-policy
dc.sourceWeb of Science
dc.subjectConnectivity in graphs
dc.subjectRemovable paths and cycles
dc.subjectNon-separating paths and cycles
dc.subjectParity in path and cycles
dc.subjectGraphs
dc.subjectConnectivity
dc.titleRemovable paths and cycles with parity constraints
dc.typeArtículos de revistas


Este ítem pertenece a la siguiente institución