BZPEERSource author record
Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.
Catalog footprint
Published work
We prove that for every tree T of radius h, there is an integer c such that every T-minor-free graph is contained in H⊠Kc for some graph H with pathwidth at most 2h−1. This is a qualitative strengthening of the Excluded Tree Minor Theorem of Robertson and Seymour (GM I). We show that radius is the right parameter to consider in this setting, and 2h−1 is the best possible bound.
A graph H is an induced subgraph of a graph G if a graph isomorphic to H can be obtained from G by deleting vertices. Recently, there has been significant interest in understanding the unavoidable induced subgraphs for graphs of large treewidth. Motivated by this work, we consider the analogous problem for pathwidth: what are the unavoidable induced subgraphs for graphs of large pathwidth? While resolving this question in the general setting looks challenging, we prove various results for sparse graphs. In particular, we show that every graph with bounded maximum degree and sufficiently large pathwidth contains a subdivision of a large complete binary tree or the line graph of a subdivision of a large complete binary tree as an induced subgraph. Similarly, we show that every graph excluding a fixed minor and with sufficiently large pathwidth contains a subdivision of a large complete binary tree or the line graph of a subdivision of a large complete binary tree as an induced subgraph. Finally, we present a characterisation for when a hereditary class defined by a finite set of forbidden induced subgraphs has bounded pathwidth.
The odd chromatic number and the conflict-free chromatic number are new graph parameters introduced by Petruševski and Škrekovski [2021] and Fabrici, Lužar, Rindošová and Soták [2022] respectively. In this note, we show that graphs with bounded 2-strong colouring number have bounded odd chromatic number and bounded conflict-free chromatic number. This implies that graph classes with bounded expansion have bounded odd chromatic number and bounded conflict-free chromatic number. Moreover, it follows by known results that the odd chromatic number and the conflict-free chromatic number of k-planar graphs is O(k) which improves a recent result of Dujmović, Morin and Odak [2022].
We show that many graphs with bounded treewidth can be described as subgraphs of the strong product of a graph with smaller treewidth and a bounded-size complete graph. To this end, define the "underlying treewidth" of a graph class G to be the minimum non-negative integer c such that, for some function f, for every graph G∈G there is a graph H with tw(H)≤c such that G is isomorphic to a subgraph of H⊠Kf(tw(G)). We introduce disjointed coverings of graphs and show they determine the underlying treewidth of any graph class. Using this result, we prove that the class of planar graphs has underlying treewidth 3; the class of Ks,t-minor-free graphs has underlying treewidth s (for t≥max{s,3}); and the class of Kt-minor-free graphs has underlying treewidth t−2. In general, we prove that a monotone class has bounded underlying treewidth if and only if it excludes some fixed topological minor. We also study the underlying treewidth of graph classes defined by an excluded subgraph or excluded induced subgraph. We show that the class of graphs with no H subgraph has bounded underlying treewidth if and only if every component of H is a subdivided star, and that the class of graphs with no induced H subgraph has bounded underlying treewidth if and only if every component of H is a star.
The planar graph product structure theorem of Dujmović, Joret, Micek, Morin, Ueckerdt, and Wood [J. ACM 2020] states that every planar graph is a subgraph of the strong product of a graph with bounded treewidth and a path. This result has been the key tool to resolve important open problems regarding queue layouts, nonrepetitive colourings, centered colourings, and adjacency labelling schemes. In this paper, we extend this line of research by utilizing shallow minors to prove analogous product structure theorems for several beyond planar graph classes. The key observation that drives our work is that many beyond planar graphs can be described as a shallow minor of the strong product of a planar graph with a small complete graph. In particular, we show that powers of planar graphs, k-planar, (k,p)-cluster planar, fan-planar and k-fan-bundle planar graphs have such a shallow-minor structure. Using a combination of old and new results, we deduce that these classes have bounded queue-number, bounded nonrepetitive chromatic number, polynomial p-centred chromatic numbers, linear strong colouring numbers, and cubic weak colouring numbers. In addition, we show that k-gap planar graphs have at least exponential local treewidth and, as a consequence, cannot be described as a subgraph of the strong product of a graph with bounded treewidth and a path.
A squaregraph is a plane graph in which each internal face is a 4-cycle and each internal vertex has degree at least 4. This paper proves that every squaregraph is isomorphic to a subgraph of the semi-strong product of an outerplanar graph and a path. We generalise this result for infinite squaregraphs, and show that this is best possible in the sense that "outerplanar graph" cannot be replaced by "forest".
We describe a family of graphs with queue-number at most 4 but unbounded stack-number. This resolves open problems of Heath, Leighton and Rosenberg (1992) and Blankenship and Oporowski (1999).
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.