Item request has been placed! ×
Item request cannot be made. ×
loading  Processing Request

Removable cycles in non-bipartite graphs

Item request has been placed! ×
Item request cannot be made. ×
loading   Processing Request
اقرأ أكثر حفظ في قائمتي
  • معلومة اضافية
    • Contributors:
      Algorithms, simulation, combinatorics and optimization for telecommunications (MASCOTTE); Inria Sophia Antipolis - Méditerranée (CRISAM); Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED); Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S); Université Nice Sophia Antipolis (... - 2019) (UNS); COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS); COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S); COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA); Université Nice Sophia Antipolis (1965 - 2019) (UNS); COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS)
    • بيانات النشر:
      HAL CCSD, 2009.
    • الموضوع:
      2009
    • نبذة مختصرة :
      International audience; 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.
    • ISSN:
      0095-8956
      1096-0902
    • Rights:
      OPEN
    • الرقم المعرف:
      edsair.doi.dedup.....adb15f11e8cd3b8fc0277bf95396392f