7 papers
Countable Graphs with Finite Path-width: Characterisation and Universality
Tony Huynh, Freddie Illingworth, Nikolai Karol +4
We study path-width and the closely related parameter line-width in countably infinite graphs. Our first result characterises the graphs of finite path-width: they are the graphs t…
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…
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…
Structure of -Matching-Planar Graphs
Kevin Hendrey, Nikolai Karol, David R. Wood
For , we define a simple topological graph (that is, a graph drawn in the plane such that every pair of edges intersect at most once, including endpoints) to be…
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 for some graphs and both with treewidth 2. This resolves a question of Liu, Norin and W…
Restriction on minimum degree in the contractible sets problem
Nikolai Karol
Let be a -connected graph. A set is called contractible if is a connected graph and is a -connected graph. In 1994, McCuaig and Ota conjec…
An existence criterion for a cycle such that the vertex set beyond this cycle is independent
Nikolai Karol
We prove that if is a 2-connected graph with then has a cycle such that is independent. This result is best possible in t…