(J'ai posté cette question sur MathOverflow il y a deux semaines, mais jusqu'à présent sans réponse rigoureuse) J'ai une question sur les mesures de largeur de graphique des graphiques simples non dirigés. Il est bien connu que les cographes (graphes qui peuvent être construits par les opérations...
J'essaie de comprendre certains concepts sur la décomposition modulaire et les graphiques à largeur de clique . Dans cet article ("On P4-tidy graphs"), il y a une preuve de la façon de résoudre des problèmes d'optimisation comme le nombre de cliques ou le nombre chromatique en utilisant la...
Quand on nous donne une décomposition arborescente d'un graphe de largeur , il y a plusieurs façons de le rendre "agréable". En particulier, il est connu qu'il est possible de le transformer en une décomposition d'arbre où l'arbre est binaire et sa hauteur est . Ceci peut être réalisé tout en...
Soit une classe de graphiques avec une largeur de clique bornée. Dans chaque graphique en G, certaines arêtes sont contractées (par exemple au hasard). La largeur de la clique est-elle toujours limitée?ggGggG Dans le cas où il n'est (en général) plus délimité, je serais très intéressé par un...
CMSOL est la logique de deuxième ordre monadique, c'est-à-dire une logique de graphiques où le domaine est l'ensemble des sommets et des arêtes, il y a des prédicats pour la contiguïté des sommets et les incidences des arêtes et des sommets, il y a une quantification sur les arêtes, les sommets,...