• DocumentCode
    3649976
  • Title

    Finding an even hole in a graph

  • Author

    M. Conforti;G. Cornuejols;A. Kapoor;K. Vuskovic

  • Author_Institution
    Dipt. di Matematica, Padova Univ., Italy
  • fYear
    1997
  • Firstpage
    480
  • Lastpage
    485
  • Abstract
    A hole in a graph is a chordless cycle of length greater than three. In this paper we present a decomposition theorem for graphs that contain no even hole. This theorem yields a polytime algorithm to recognize whether a graph contains an even hole.
  • Keywords
    "Bismuth","Mathematics","Zinc"
  • Publisher
    ieee
  • Conference_Titel
    Foundations of Computer Science, 1997. Proceedings., 38th Annual Symposium on
  • ISSN
    0272-5428
  • Print_ISBN
    0-8186-8197-7
  • Type

    conf

  • DOI
    10.1109/SFCS.1997.646136
  • Filename
    646136
    • Link To Document
    https://search.isc.ac/dl/search/defaultta.aspx?DTC=49&DC=3649976