A structure theorem for graphs with no cycle with a unique chord and its consequences - HAL-SHS - Sciences de l'Homme et de la Société Accéder directement au contenu
Autre Publication Scientifique Année : 2008

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

Nicolas Trotignon
Kristina Vuskovic
  • Fonction : Auteur
  • PersonId : 838102

Résumé

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.
Soit C la classe de graphes ne contenant pas de cycle avec une seule corde en tant que sous-graphe induit. Nous montrons que tout graphe de C est ou bien "basique" ou bien "décomposable". Par graphe basique, nous entendons : clique, graphe biparti avec un côté ne contenant que des sommets de degré 2, et sous-graphe induit du graphe de Petersen ou de Heawood. Par décomposable, nous entendons : possédant un sommet ou une paire de sommets d'articulation ou possédant un 1-joint. Notre résultat est un théorème de structure, c'est-à-dire qu'il est réversible. Nous prouvons quelques conséquences : la preuve que tout graphe de C est ou bien coloriable avec 3 couleurs, ou bien avec ω couleurs où ω est la taille d'une plus grande clique. Nous donnons un algorithme de coloration en O(nm). Nous donnons un algorithme de reconnaissance en O(nm) pour la classe C. Cet algorithme répond à des questions intéressantes concernant la détection de sous-graphes induits.
Fichier principal
Vignette du fichier
B08021.pdf (499.91 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

halshs-00265957 , version 1 (20-03-2008)

Identifiants

  • HAL Id : halshs-00265957 , version 1

Citer

Nicolas Trotignon, Kristina Vuskovic. A structure theorem for graphs with no cycle with a unique chord and its consequences. 2008. ⟨halshs-00265957⟩
146 Consultations
159 Téléchargements

Partager

Gmail Facebook X LinkedIn More