1 citations · 3 across the 4 of their papers we have counts for
13 papers · 1 filter
Burling graphs in graphs with large chromatic number
Tara Abrishami, Marcin Briański, James Davies +4
A graph class is -bounded if the only way to force large chromatic number in graphs from the class is by forming a large clique. In the 1970s, Erdős conjectured that intersectio…
A simple layered-wheel-like construction
Maria Chudnovsky, David Fischer, Sepehr Hajebi +2
In recent years, there has been significant interest in characterizing the induced subgraph obstructions to bounded treewidth and pathwidth. While this has recently been resolved f…
Polynomial-time recognition and maximum independent set in Burling graphs
Paweł Rzążewski, Bartosz Walczak
A Burling graph is an induced subgraph of some graph in Burling's construction of triangle-free high-chromatic graphs. Equivalently, a Burling graph is a graph that admits a so-cal…
Excluding a clique or a biclique in graphs of bounded induced matching treewidth
Tara Abrishami, Marcin Briański, Jadwiga Czyżewska +4
For a tree decomposition of a graph , let denote the maximum size of an induced matching in with the property that some bag of c…
Cliquewidth and dimension
Gwenaël Joret, Piotr Micek, Michał Pilipczuk +1
We prove that every poset with bounded cliquewidth and with sufficiently large dimension contains the standard example of dimension as a subposet. This applies in particular to…
Tight bound on treedepth in terms of pathwidth and longest path
Meike Hatzel, Gwenaël Joret, Piotr Micek +3
We show that every graph with pathwidth strictly less than that contains no path on vertices as a subgraph has treedepth at most . The bound is best possible up to…