5 papers
Circular-arc graphs and the Helly property
Jan Derbisz, Tomasz Krawczyk
In this paper we investigate some problems related to the Helly properties of circular-arc graphs, which are defined as intersection graphs of arcs of a fixed circle. As such, circ…
Characterization of Chordal Circular-arc Graphs: I. Split Graphs
Yixin Cao, Jan Derbisz, Tomasz Krawczyk
The most elusive problem around the class of circular-arc graphs is identifying all minimal graphs that are not in this class. The main obstacle is the lack of a systematic way of…
Beyond circular-arc graphs -- recognizing lollipop graphs and medusa graphs
Deniz Ağaoğlu Çağırıcı, Onur Çağırıcı, Jan Derbisz +5
In 1992 Biró, Hujter and Tuza introduced, for every fixed connected graph , the class of -graphs, defined as the intersection graphs of connected subgraphs of some subdivisio…
A polynomial kernel for vertex deletion into bipartite permutation graphs
Jan Derbisz
A permutation graph can be defined as an intersection graph of segments whose endpoints lie on two parallel lines and , one on each. A bipartite permutation graph…
Vertex deletion into bipartite permutation graphs
Łukasz Bożyk, Jan Derbisz, Tomasz Krawczyk +2
A permutation graph can be defined as an intersection graph of segments whose endpoints lie on two parallel lines and , one on each. A bipartite permutation graph is a p…