La largeur d'arbre implique- t-elle l'existence d'un mineur?

Soit $k$ fixé et $G$ soit un graphe (connecté). Si je ne me trompe pas, il résulte des travaux de Bodlaender [1, Theorem 3.11] que si la largeur d'arbre de $G$ est à peu près au moins $2k^3$ , alors $G$ contient une étoile $K_{1,k}$ tant que mineur.

Pouvons-nous rendre le terme $2k^3$ plus petit? Autrement dit, la largeur d'arbre d'au moins $k$ implique-t-elle déjà l'existence d'un $K_{1,k}$ -mineur? Y a-t-il une preuve quelque part?

[1] Bodlaender, HL (1993). Sur des tests mineurs de temps linéaire avec recherche en profondeur d'abord. Journal of Algorithms, 14 (1), 1-23.

graph-theory treewidth graph-minor Juho
la source

Un résultat lié de façon lâche à partir de Demaine et Hajiaghayi : Pour un graphique fixe , tout graphique libre--minor de treewidth a une grille graphique mineur.

H

$H$

H

$H$

w

$w$

Ω (w) \times Ω (w)

$\Omega(w) \times \Omega(w)$

mhum

@mhum la constante dans le dépend exponentiellement de, donc appliquer directement cela donnera une limite inférieure à .

Ω

$\Omega$

| H |

$|H|$

2 k^{3}

$2k^3$

daniello

@daniello C'est bien le cas. La constante n'est pas très agréable et la spécialisation vers les graphiques sans n'est pas non plus grande. Je voulais juste signaler un résultat vaguement lié.

H

$H$

mhum

Il est en effet vrai que tout graphe sans mineur a une largeur d'arbre au plus . Nous le prouvons ci-dessous, d'abord quelques définitions: $G$ $K_{1,k}$ $k-1$

Laissez soit la largeur arborescente de et soit la taille maximale d'une clique dans . Un graphe est une triangulation de si est un sous-graphe de et est corde (c'est-à-dire n'a pas de cycles induits sur au moins sommets). Une triangulation de est une triangulation minimale si aucun sous - graphe propre de est une triangulation de . Un sous-ensemble de sommets de est une clique maximale potentielle $tw(G)$ $G$ $\omega(G)$ $G$ $H$ $G$ $G$ $H$ $H$ $4$ $H$ $G$ $H$ $G$ $X$ $G$ s'il existe une triangulation minimale de tel que est une clique maximale de . Il est bien connu que Ici, le minimum est pris en charge tous les triangulations minimales de . $H$ $G$ $X$ $H$

t w (G) = min_{H} ω (H) - 1

$tw(G) = \min_{H} \omega(H) - 1$

H

$H$

G

$G$

La formule ci-dessus implique que pour prouver que il suffit de prouver que toutes les cliques maximales potentielles de ont une taille au plus . Nous le prouvons maintenant. Soit une clique maximale potentielle de , et supposons que . $tw(G) \leq k-1$ $G$ $k$ $X$ $G$ $|X| \geq k+1$

Nous utiliserons la caractérisation suivante des cliques maximales potentielles: un ensemble de sommets est une clique maximale potentielle dans si, et seulement si, pour chaque paire , de sommets non adjacents (distincts) dans il y a un chemin à partir de à dans avec tous ses sommets internes à l'extérieur du . Cette caractérisation se trouve dans l'article Treewidth and Minimum Fill-in: Grouping the Minimal Separators de Bouchitte et Todinca. $X$ $G$ $u$ $v$ $X$ $P_{u,v}$ $u$ $v$ $G$ $X$

Avec cette description , il est facile de tirer un mineur de . Laissez . Pour chaque sommet , soit est une arête de ou il y a un chemin à partir de à avec tous les sommets internes à l'extérieur . Pour tous les qui ne sont pas adjacents à contractez tous les sommets internes de en . On se retrouve avec un mineur de dans lequel est adjacent à tout , et $K_{1,k}$ $X$ $u \in X$ $v \in X \setminus \{u\}$ $uv$ $G$ $P_{u,v}$ $u$ $v$ $X$ $v \in X$ $u$ $P_{u,v}$ $u$ $G$ $u$ $X$ $|X| \geq k+1$ . Donc, le degré de dans ce mineur est au moins , complétant la preuve. $u$ $k$

daniello
la source

Merci Daniel! Savez-vous par hasard si le même argument (ou le résultat, vraiment) a été publié quelque part?

Juho

Je n'ai pas de référence, mais je semble me souvenir qu'un argument similaire (peut-être moins serré) pour les graphes libres est écrit quelque part. Malheureusement, je n'ai pas de pointeur plus concret.

K_{2, r}

$K_{2,r}$

daniello

La largeur d'arbre implique- t-elle l'existence d'un mineur?

Réponses: