research
∙
01/20/2023
Separating the edges of a graph by a linear number of paths
Recently, Letzter proved that any graph of order n contains a collection...
share
research
∙
09/19/2022
Gap-ETH-Tight Approximation Schemes for Red-Green-Blue Separation and Bicolored Noncrossing Euclidean Travelling Salesman Tours
In this paper, we study problems of connecting classes of points via non...
research
∙
10/14/2021
On the proper interval completion problem within some chordal subclasses
Given a property (graph class) Π, a graph G, and an integer k, the Π-com...
research
∙
09/28/2021
Generalising the achromatic number to Zaslavsky's colourings of signed graphs
The chromatic number, which refers to the minimum number of colours requ...
research
∙
08/02/2020
Tree pivot-minors and linear rank-width
Tree-width and its linear variant path-width play a central role for the...
research
∙
01/15/2020
1-planar graphs with minimum degree at least 3 have bounded girth
We show that every 1-planar graph with minimum degree at least 4 has gir...
research
∙
12/03/2019
Jones' Conjecture in subcubic graphs
We confirm Jones' Conjecture for subcubic graphs. Namely, if a subcubic ...
research
∙
07/07/2019
Complexity of planar signed graph homomorphisms to cycles
We study homomorphism problems of signed graphs. A signed graph is an un...
research
∙
05/07/2019
The structure of graphs with given number of blocks and the maximum Wiener index
The Wiener index (the distance) of a connected graph is the sum of dista...
research
∙
05/07/2019
Graphs with the second and third maximum Wiener index over the 2-vertex connected graphs
Wiener index, defined as the sum of distances between all unordered pair...
research
∙
05/06/2019
Partitioning sparse graphs into an independent set and a graph with bounded size components
We study the problem of partitioning the vertex set of a given graph so ...
research
∙
12/12/2018
On the unavoidability of oriented trees
A digraph is n-unavoidable if it is contained in every tournament of or...
research
∙
11/23/2017
Vertex partitions of (C_3,C_4,C_6)-free planar graphs
A graph is (k_1,k_2)-colorable if its vertex set can be partitioned into...
research
∙
06/22/2015