Removable cycles in non-bipartite graphs

dc.creatorKawarabayashi, K
dc.creatorReed, B
dc.creatorLee, O
dc.date2009
dc.dateJAN
dc.date2014-11-19T10:14:07Z
dc.date2015-11-26T18:02:14Z
dc.date2014-11-19T10:14:07Z
dc.date2015-11-26T18:02:14Z
dc.date.accessioned2018-03-29T00:43:54Z
dc.date.available2018-03-29T00:43:54Z
dc.identifierJournal Of Combinatorial Theory Series B. Academic Press Inc Elsevier Science, v. 99, n. 1, n. 30, n. 38, 2009.
dc.identifier0095-8956
dc.identifierWOS:000261590400004
dc.identifier10.1016/j.jctb.2008.03.007
dc.identifierhttp://www.repositorio.unicamp.br/jspui/handle/REPOSIP/70883
dc.identifierhttp://www.repositorio.unicamp.br/handle/REPOSIP/70883
dc.identifierhttp://repositorio.unicamp.br/jspui/handle/REPOSIP/70883
dc.identifier.urihttp://repositorioslatinoamericanos.uchile.cl/handle/2250/1292176
dc.descriptionConselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq)
dc.descriptionFundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP)Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq)
dc.descriptionIn this paper we prove the following result. Suppose that s and t are vertices of a 3-connected graph G such that G - s - t is not bipartite and there is no cutset X of size three in G for which some component U of G - X is disjoint from is. t). Then either (1) G contains an induced path P from s to t such that G - V (P) is not bipartite or (2) G can be embedded in the plane so that every odd face contains one of s or t. Furthermore, if (1) holds then we can insist that G - V(P) is connected, while if G is 5-connected then (1) must hold and P can be chosen so that G - V(P) is 2-connected. (C) 2008 Published by Elsevier Inc.
dc.description99
dc.description1
dc.description30
dc.description38
dc.descriptionJapan Society for the Promotion of Science
dc.descriptionC C Foundation
dc.descriptionKayamori Foundation
dc.descriptionInoue Research Award
dc.descriptionConselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq)
dc.descriptionFundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP)
dc.descriptionConselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq)
dc.descriptionFundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP)Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq)
dc.descriptionCNPq [490333/2004-4, 471460/2004-4, 478470/2006-1, 301310/2005-0]
dc.descriptionFAPESP [09925/2003-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.subjectLovasz' conjecture
dc.subjectRemovable paths
dc.subjectRemovable cycles
dc.subjectOdd cycles
dc.subjectPaths
dc.titleRemovable cycles in non-bipartite graphs
dc.typeArtículos de revistas


Este ítem pertenece a la siguiente institución