A structure theorem for graphs with no cycle with a unique chord and its consequences

Nicolas Trotignon () and Kristina Vuškovic ()
Additional contact information
Nicolas Trotignon: Centre d'Economie de la Sorbonne, https://centredeconomiesorbonne.univ-paris1.fr
Kristina Vuškovic: University of Leeds

Documents de travail du Centre d'Economie de la Sorbonne from Université Panthéon-Sorbonne (Paris 1), Centre d'Economie de la Sorbonne

Abstract: We give a structural description of the class C of graphs that do not contain a cycle with a unique chord as an induced subgraph. Our main theorem states that any connected graph in C is a either in some simple basic class or has a decomposition. Basic classes are cliques, bipartite graphs with one side containing only nodes of degree two and induced subgraph of the famous Heawood or Petersen graph. Decompositions are node cutsets consisting of one or two nodes and edge cutsets called 1-joins. Our decomposition theorem actually gives a complete structure theorem for C, i.e. every graph in C can be built from basic graphs that can be explicitly constructed, and gluing them together by prescribed composition operations; and all graphs built this way are in C. This has several consequences: an O(nm)-time algorithm to decide whether a graph is in C, an O(n+m)-time algorithm that finds a maximum clique of any graph in C and an O(nm)-time coloring algorithm for graphs in C. We prove that every graph in C is either 3-colorable or has a coloring with ? colors where ? is the size of a largest clique. The problem of finding a maximum stable set for a graph in C is known to be NP-hard

Keywords: Cycle with a unique chord; decomposition; structure; detection; recognition; Heawood graph; Petersen graph; coloring. (search for similar items in EconPapers)
Pages: 43 pages
Date: 2008-03
New Economics Papers: this item is included in nep-net
References: Add references at CitEc
Citations:

Downloads: (external link)
ftp://mse.univ-paris1.fr/pub/mse/CES2008/B08021.pdf (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:mse:cesdoc:b08021

Access Statistics for this paper

More papers in Documents de travail du Centre d'Economie de la Sorbonne from Université Panthéon-Sorbonne (Paris 1), Centre d'Economie de la Sorbonne Contact information at EDIRC.
Bibliographic data for series maintained by Lucie Label ().