Research Seminar Discrete Mathematics together with the chairs Algorithmic Mathematics, Engineering Mathematics and Numerical Optimization, Theoretical Computer Science

Sessions: Wednesdays, 9.15–10.45 a.m. in HG 0.19

Upcoming Talks

DateNameTopic
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.