On graphs that do not contain a subdivision of the complete graph on four vertices as an induced subgraph

Benjamin Lévêque (1) , Frédéric Maffray (1) , Nicolas Trotignon (2)

1 G-SCOP_OC - Optimisation Combinatoire
2 CES - Centre d'économie de la Sorbonne

We prove a decomposition theorem for graphs that do not contain a subdivision of the complete graph on four vertices as an induced subgraph.

Nous donnons un théorème de décomposition pour les graphes ne contenant pas de subdivision du graphe complet sur quatre sommets en tant que sous-graphe induit.

Mots clés: decomposition; Induced; subgraph

Mots clés: Sous-graphe; induit; décomposition

Domaines: Economies et finances; Mathématique discrète [cs.DM]; Combinatoire [math.CO]

Benjamin Lévêque, Frédéric Maffray, Nicolas Trotignon. On graphs that do not contain a subdivision of the complete graph on four vertices as an induced subgraph. 2007. ⟨halshs-00180961⟩