N. Karol

collaborators

5 papers

math.CO2026

Restriction on minimum degree in the contractible sets problem

Nikolai Karol

Let $G$ be a $3$ -connected graph. A set $W \subset V (G)$ is called contractible if $G (W)$ is a connected graph and $G - W$ is a $2$ -connected graph. In 1994, McCuaig and Ota conjec…

math.CO2026

Sparse String Graphs and Region Intersection Graphs over Minor-Closed Classes have Linear Expansion

Nikolai Karol, David R. Wood

We prove that sparse string graphs in a fixed surface have linear expansion. We extend this result to the more general setting of sparse region intersection graphs over any proper…

math.CO2025

String Graphs: Product Structure and Localised Representations

Nikolai Karol

We investigate string graphs through the lens of graph product structure theory, which describes complicated graphs as subgraphs of strong products of simpler building blocks. A gr…

math.CO2025

Structure of $k$ -Matching-Planar Graphs

Kevin Hendrey, Nikolai Karol, David R. Wood

For $k ⩾ 0$ , we define a simple topological graph $G$ (that is, a graph drawn in the plane such that every pair of edges intersect at most once, including endpoints) to be…

math.CO2025

Treewidth 2 in the Planar Graph Product Structure Theorem

Marc Distel, Kevin Hendrey, Nikolai Karol +2

We prove that every planar graph is contained in $H_{1} ⊠ H_{2} ⊠ K_{2}$ for some graphs $H_{1}$ and $H_{2}$ both with treewidth 2. This resolves a question of Liu, Norin and W…

Restriction on minimum degree in the contractible sets problem

Sparse String Graphs and Region Intersection Graphs over Minor-Closed Classes have Linear Expansion

String Graphs: Product Structure and Localised Representations

Structure of k-Matching-Planar Graphs

Treewidth 2 in the Planar Graph Product Structure Theorem

Structure of $k$ -Matching-Planar Graphs