3 citations · 9 across the 10 of their papers we have counts for
Showing 2023Show all
3 papers · 1 filter
cs.DS2023
Exploration of graphs with excluded minors
Julia Baligacs, Yann Disser, Irene Heinrich +1
We study the online graph exploration problem proposed by Kalyanasundaram and Pruhs (1994) and prove a constant competitive ratio on minor-free graphs. This result encompasses and…
math.CO2023
Twin-width of graphs with tree-structured decompositions
Irene Heinrich, Simon Raßmann
The twin-width of a graph measures its distance to co-graphs and generalizes classical width concepts such as tree-width or rank-width. Since its introduction in 2020 (Bonnet et. a…
math.CO2023
Countable ultrahomogeneous graphs on two imprimitive color classes
Sofia Brenner, Irene Heinrich
We classify the countable ultrahomogeneous 2-vertex-colored graphs in which the color classes are imprimitive, i.e., up to complementation they form disjoint unions of cliques. Thi…