Removable cycles in non-bipartite graphs

K. Kawarabayashi O. Lee Bruce Reed 1, 2
2 MASCOTTE - Algorithms, simulation, combinatorics and optimization for telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
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 s,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.
Type de document :
Article dans une revue
Journal of Combinatorial Theory, Series B, Elsevier, 2009, 99, pp.30―38. 〈10.1016/j.jctb.2008.03.007〉
Liste complète des métadonnées

https://hal.inria.fr/hal-00795287
Contributeur : Alain Monteil <>
Soumis le : mercredi 27 février 2013 - 17:01:14
Dernière modification le : mercredi 27 février 2013 - 17:01:14

Identifiants

Collections

Citation

K. Kawarabayashi, O. Lee, Bruce Reed. Removable cycles in non-bipartite graphs. Journal of Combinatorial Theory, Series B, Elsevier, 2009, 99, pp.30―38. 〈10.1016/j.jctb.2008.03.007〉. 〈hal-00795287〉

Partager

Métriques

Consultations de la notice

92