Please use this identifier to cite or link to this item: http://repositorio.unicamp.br/jspui/handle/REPOSIP/70883
Type: Artigo de periódico
Title: Removable cycles in non-bipartite graphs
Author: Kawarabayashi, K
Reed, B
Lee, O
Abstract: In 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.
Subject: Lovasz' conjecture
Removable paths
Removable cycles
Odd cycles
Country: EUA
Editor: Academic Press Inc Elsevier Science
Rights: fechado
Identifier DOI: 10.1016/j.jctb.2008.03.007
Date Issue: 2009
Appears in Collections:Artigos e Materiais de Revistas Científicas - Unicamp

Files in This Item:
File Description SizeFormat 
WOS000261590400004.pdf178.65 kBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.