K-arbre
En théorie des graphes, un k- arbre est un type de graphe non orienté. Un graphe est un k-arbre s'il peut être obtenu de la manière suivante :  on part du graphe complet à ( k + 1) sommets, puis on ajoute des sommets tels que, pour un sommet v ajouté, v a exactement k voisins dans le graphe au moment de l'ajout, et ces voisins forment une clique.

Caractérisations 
Les k-arbres sont exactement les graphes de largeur arborescente  donnée, maximaux au sens que l'on ne peut pas ajouter d'arêtes sans augmenter leur largeur arborescente. Ce sont aussi exactement les graphes cordaux dont toutes les cliques maximales ont la même taille k + 1 et dont tous les séparateurs de cliques minimaux ont également tous la même taille k .

Classes de graphes associées 
Les 1-arbres sont les arbres non enracinés. Les 2-arbres sont exactement les graphes série-parallèles maximaux. Les graphes planaires externes maximaux sont des 2-arbres. Les 3-arbres planaires sont également connus sous le nom de réseaux apolliniens. Les graphes qui ont une largeur arborescente au plus k sont exactement les sous-graphes des k-arbres, et pour cette raison ils sont appelés .

Les graphes formés par les arêtes et les sommets de polytopes empilés de dimension k (qui sont des polytopes formés en partant d'un simplexe puis en collant à plusieurs reprises des simplexes sur les faces du polytope) sont des k-arbres lorsque k ≥ 3. Ce processus de collage imite la construction de k-arbres en ajoutant des sommets à une clique. Un k-arbre est le graphe d'un polytope empilé si et seulement s'il n'existe pas  trois  cliques de k + 1) sommets qui ont k sommets en commun.

Notes et références

Bibliographie additionnelle 
 
 .

Famille de graphes
Graphe parfait
Arbre (graphe)