research
∙
07/05/2023
Maximum edge colouring problem on graphs that exclude a fixed minor
The maximum edge colouring problem considers the maximum colour assignme...
share
research
∙
04/25/2023
A note on local search for hitting sets
Let π be a property of pairs (G,Z), where G is a graph and Z⊆ V(G). In t...
research
∙
03/09/2023
Embedded graph 3-coloring and flows
A graph drawn in a surface is a near-quadrangulation if the sum of the l...
research
∙
01/16/2023
An efficient implementation and a strengthening of Alon-Tarsi list coloring method
As one of the first applications of the polynomial method in combinatori...
research
∙
05/25/2022
Square roots of nearly planar graphs
We prove that it is NP-hard to decide whether a graph is the square of a...
research
∙
04/19/2022
Representation of short distances in structurally sparse graphs
A partial orientation H⃗ of a graph G is a weak r-guidance system if for...
research
∙
03/15/2022
On Comparable Box Dimension
Two boxes in ℝ^d are comparable if one of them is a subset of a translat...
research
∙
05/04/2021
Approximation schemes for bounded distance problems on fractionally treewidth-fragile graphs
We give polynomial-time approximation schemes for monotone maximization ...
research
∙
03/31/2021
Weak Coloring Numbers of Intersection Graphs
Weak and strong coloring numbers are generalizations of the degeneracy o...
research
∙
03/15/2021
Approximation metatheorem for fractionally treewidth-fragile graphs
Baker's technique is a powerful tool for designing polynomial-time appro...
research
∙
10/04/2020
On decidability of hyperbolicity
We prove that a wide range of coloring problems in graphs on surfaces ca...
research
∙
01/24/2020
Notes on Graph Product Structure Theory
It was recently proved that every planar graph is a subgraph of the stro...
research
∙
01/08/2020
Induced odd cycle packing number, independent sets, and chromatic number
The induced odd cycle packing numberiocp(G) of a graph G is the maximum ...
research
∙
09/26/2019
Coloring near-quadrangulations of the cylinder and the torus
Let G be a simple connected plane graph and let C_1 and C_2 be cycles in...
research
∙
03/13/2019
Bounded maximum degree conjecture holds precisely for c-crossing-critical graphs with c ≤ 12
We study c-crossing-critical graphs, which are the minimal graphs that r...
research
∙
02/11/2019
Flexibility of planar graphs of girth at least six
Let G be a planar graph with a list assignment L. Suppose a preferred co...
research
∙
02/08/2019
Flexibility of triangle-free planar graphs
Let G be a planar graph with a list assignment L. Suppose a preferred co...
research
∙
01/07/2019
Baker game and polynomial-time approximation schemes
Baker devised a technique to obtain approximation schemes for many optim...
research
∙
03/29/2018
Least conflict choosability
Given a multigraph, suppose that each vertex is given a local assignment...
research
∙
03/05/2018
Structure and generation of crossing-critical graphs
We study c-crossing-critical graphs, which are the minimal graphs that r...
research
∙
10/27/2017
On distance r-dominating and 2r-independent sets in sparse graphs
Dvorak (2013) gave a bound on the minimum size of a distance r dominatin...
research
∙
10/09/2017
On classes of graphs with strongly sublinear separators
For real numbers c,epsilon>0, let G_c,epsilon denote the class of graphs...
research
∙
09/12/2017