10 citations · 44 across the 41 of their papers we have counts for
Showing 2014Show all
2 papers · 1 filter
cs.LO2014
Universal covers, color refinement, and two-variable counting logic: Lower bounds for the depth
Andreas Krebs, Oleg Verbitsky
Given a connected graph and its vertex , let denote the universal cover of obtained by unfolding into a tree starting from . Let be the minimum…
cs.CC2014★ 4 cited
On the Isomorphism Problem for Helly Circular-Arc Graphs
Johannes Köbler, Sebastian Kuhnert, Oleg Verbitsky
The isomorphism problem is known to be efficiently solvable for interval graphs, while for the larger class of circular-arc graphs its complexity status stays open. We consider the…