Peter Gartland

activity

20182024

_{k}

-Free Graphs in Quasi-Polynomial Time

5 citations · 5 across the 3 of their papers we have counts for

collaborators

Showing math.COShow all

4 papers · 1 filter

math.CO2024

Tree Independence Number IV. Even-hole-free Graphs

Maria Chudnovsky, Peter Gartland, Sepehr Hajebi +2

We prove that the tree independence number of every even-hole-free graph is at most polylogarithmic in its number of vertices. More explicitly, we prove that there exists a constan…

math.CO2024

Induced subgraphs and tree decompositions XV. Even-hole-free graphs with bounded clique number have logarithmic treewidth

Maria Chudnovsky, Peter Gartland, Sepehr Hajebi +2

We prove that for every integer $t \geq 1$ there exists an integer $c_{t} \geq 1$ such that every $n$ -vertex even-hole-free graph with no clique of size $t$ has treewidth at most $c_t\…

math.CO2023

On Induced Versions of Menger's Theorem on Sparse Graphs

Peter Gartland, Tuukka Korhonen, Daniel Lokshtanov

Let $A$ and $B$ be sets of vertices in a graph $G$ . Menger's theorem states that for every positive integer $k$ , either there exists a collection of $k$ vertex-disjoint paths betwe…

math.CO2018

A New Characterization of $V$ -Posets

Joshua Cooper, Peter Gartland, Hays Whitlatch

In 2016, Hasebe and Tsujie gave a recursive characterization of the set of induced $N$ -free and bowtie-free posets; Misanantenaina and Wagner studied these orders further, naming t…

Tree Independence Number IV. Even-hole-free Graphs

Induced subgraphs and tree decompositions XV. Even-hole-free graphs with bounded clique number have logarithmic treewidth

On Induced Versions of Menger's Theorem on Sparse Graphs

A New Characterization of V-Posets

A New Characterization of $V$ -Posets