Paper Info
Title
Excluding a Ladder
Abstract
A ladder is a 2 × k grid graph. When does a graph class $${\cal C}$$ exclude some ladder as a minor? We show that this is the case if and only if all graphs G in $${\cal C}$$ admit a proper vertex coloring with a bounded number of colors such that for every 2-connected subgraph H of G, there is a color that appears exactly once in H. This type of vertex coloring is a relaxation of the notion of centered coloring, where for every connected subgraph H of G, there must be a color that appears exactly once in H. The minimum number of colors in a centered coloring of G is the treedepth of G, and it is known that classes of graphs with bounded treedepth are exactly those that exclude a fixed path as a subgraph, or equivalently, as a minor. In this sense, the structure of graphs excluding a fixed ladder as a minor resembles the structure of graphs without long paths. Another similarity is as follows: It is an easy observation that every connected graph with two vertex-disjoint paths of length k has a path of length k+1. We show that every 3-connected graph which contains as a minor a union of sufficiently many vertex-disjoint copies of a 2×k grid has a 2×(k+1) grid minor. Our structural results have applications to poset dimension. We show that posets whose cover graphs exclude a fixed ladder as a minor have bounded dimension. This is a new step towards the goal of understanding which graphs are unavoidable as minors in cover graphs of posets with large dimension.
Year
DOI
Venue
2022
10.1007/s00493-021-4592-8
Combinatorica
Keywords
DocType
Volume
05C83, 06A07
Journal
42
Issue
ISSN
Citations 
3
0209-9683
0
PageRank 
References 
Authors
0.34
11
5
Name
Order
Citations
PageRank
Huynh Tony100.68
Gwenaël Joret219628.64
Micek Piotr300.34
Seweryn Michał T.400.34
Paul Wollan529626.33