Degré maximal dans les graphes série-parallèles non-étiquetés aléatoires
Zéphyr Salvy (TU Wien, Autriche)Les graphes série-parallèles sont les graphes qui n’admettent pas \(K_4\) comme mineur. La classe des graphes série-parallèles est une sous-classe des graphes planaires, généralement plus simple à analyser. Or, les classes non-étiquetées sont en général plus difficiles à traiter que leurs homologues étiquetées, en raison du rôle joué par la symétrie. Pour cette raison, l’étude des graphes série-parallèles non étiquetés constitue une étape naturelle vers celle, plus délicate, des graphes planaires non étiquetés. En combinant des méthodes de pointage de cycle, des outils de combinatoire analytique et un générateur de Pólya–Boltzmann, nous obtenons une estimation précise du degré maximal d’un graphe série-parallèle non étiqueté uniforme. Ce travail est une collaboration avec Michael Drmota, Veronika Kraus, Konstantinos Panagiotou et Benedikt Stufler.