19 citations · 63 across the 12 of their papers we have counts for
8 papers · 1 filter
Algorithmic Aspects of Regular Graph Covers
Jiří Fiala, Pavel Klavík, Jan Kratochvíl +1
A graph covers a graph if there exists a locally bijective homomorphism from to . We deal with regular covers where this homomorphism is prescribed by the action of…
Graph Isomorphism Restricted by Lists
Pavel Klavik, Dušan Knop, Peter Zeman
The complexity of graph isomorphism (GraphIso) is a famous unresolved problem in theoretical computer science. For graphs and , it asks whether they are the same up to a rel…
On the Classes of Interval Graphs of Limited Nesting and Count of Lengths
Pavel Klavík, Yota Otachi, Jiří Šejnoha
In 1969, Roberts introduced proper and unit interval graphs and proved that these classes are equal. Natural generalizations of unit interval graphs called -length interval grap…
Automorphism Groups of Comparability Graphs
Pavel Klavík, Peter Zeman
Comparability graphs are graphs which have transitive orientations. The dimension of a poset is the least number of linear orders whose intersection gives this poset. The dimension…
Bounded Representations of Interval and Proper Interval Graphs
Martin Balko, Pavel Klavík, Yota Otachi
Klavik et al. [arXiv:1207.6960] recently introduced a generalization of recognition called the bounded representation problem which we study for the classes of interval and proper…
Extending Partial Representations of Circle Graphs
Steven Chaplick, Radoslav Fulek, Pavel Klavík
The partial representation extension problem is a recently introduced generalization of the recognition problem. A circle graph is an intersection graph of chords of a circle. We s…
Extending Partial Representations of Interval Graphs
Pavel Klavík, Jan Kratochvíl, Yota Otachi +2
Interval graphs are intersection graphs of closed intervals of the real-line. The well-known computational problem, called recognition, asks whether an input graph can be repre…
Extending Partial Representations of Proper and Unit Interval Graphs
Pavel Klavík, Jan Kratochvíl, Yota Otachi +4
The recently introduced problem of extending partial interval representations asks, for an interval graph with some intervals pre-drawn by the input, whether the partial representa…