Forschungsseminar Diskrete Mathematik zusammen mit den Fachgebieten Algorithmische Mathematik, Ingenieurmathematik und Numerik der Optimierung, Theoretische Informatik

Termine: Mittwochs, 9:15–10:45 Uhr im HG 0.19

Anstehende Vorträge

DatumNameThema
11.11.2026Philipp Wolf Schleicher
BTU Cottbus-Senftenberg
Optimization Problems on Graphs Close to Chordal and (Co-)Comparability Graphs

Abstracts

Philipp Wolf Schleicher: Optimization Problems on Graphs Close to Chordal and (Co-)Comparability Graphs

Beisegel, Chiarelli, Köhler, Milanič, Muršič, and Scheffler [SWAT 2024] introduced the concept of simultaneous \(\mathcal{C}\)-numbers which associate a graph class \(\mathcal{C}\) with a graph parameter. Given a graph \(G\), the simultaneous \(\mathcal{C}\)-number is the smallest number \(d\) for which there is a graph \(H\) in \(\mathcal{C}\) and a function \(L : V(G) \to \mathcal{P}(\{1, ..., d\})\) such that two vertices \(u\) and \(v\) are adjacent in \(G\) if and only if they are adjacent in \(H\) and their sets \(L(u)\) and \(L(v)\) are not disjoint. Beisegel et al. focused on the class of interval graphs, giving FPT algorithms for the problems Clique, Independent Set, and Dominating Set parameterized by the simultaneous interval number. We consider these three problems when parameterized by other simultaneous \(\mathcal{C}\)-numbers, namely for chordal graphs, comparability graphs, and co-comparability graphs.