Artículos de revistas
Removable cycles in non-bipartite graphs
Registration in:
Journal Of Combinatorial Theory Series B. Academic Press Inc Elsevier Science, v. 99, n. 1, n. 30, n. 38, 2009.
0095-8956
WOS:000261590400004
10.1016/j.jctb.2008.03.007
Author
Kawarabayashi, K
Reed, B
Lee, O
Institutions
Abstract
Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq) Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP)Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq) 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. 99 1 30 38 Japan Society for the Promotion of Science C C Foundation Kayamori Foundation Inoue Research Award Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq) Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP) Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq) Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP)Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq) CNPq [490333/2004-4, 471460/2004-4, 478470/2006-1, 301310/2005-0] FAPESP [09925/2003-5]