3 papers
math.CO2025
Trail Trap: a variant of Partizan Edge Geography
Calum Buchanan, MacKenzie Carr, Alexander Clifton +4
We study a two-player game played on undirected graphs called {\sc Trail Trap}, which is a variant of a game known as {\sc Partizan Edge Geography}. One player starts by choosing a…
cs.DS2024
Canonizing Graphs of Bounded Rank-Width in Parallel via Weisfeiler--Leman
Michael Levet, Puck Rombach, Nicholas Sieger
In this paper, we show that computing canonical labelings of graphs of bounded rank-width is in . Our approach builds on the framework of Köbler & Verbitsky (CSR…
cs.DS2024
Logarithmic Weisfeiler--Leman and Treewidth
Michael Levet, Puck Rombach, Nicholas Sieger
In this paper, we show that the -dimensional Weisfeiler--Leman algorithm can identify graphs of treewidth in rounds. This improves the result of Grohe & Ver…