***********************************
                * Princeton Discrete Math Seminar *
                ***********************************

Speaker: Martin Milanic (University of Primorska)

Thursday 26th September, 3:00 in Fine Hall 224.

Title: Tree decompositions meet induced matchings

Tree decompositions are an important tool in structural and
algorithmic graph theory, largely due to treewidth. Several more
general width parameters have been recently introduced that, unlike
treewidth, can also be bounded on dense graph classes, and for which
Maximum Independent Set and related problems can be solved in
polynomial time when the parameter is bounded. This includes
tree-independence number, introduced independently by Yolov in 2018
and by Dallard, Milanič, and Štorgel in 2021, and induced matching
treewidth, introduced by Yolov in 2018 (under the name minor-matching
hypertreewidth). Good algorithmic properties of these parameters
motivate the study of conditions for their boundedness.

The induced matching treewidth of a graph G is defined as the minimum,
over all tree decompositions of G, of the maximum size of an induced
matching all of whose edges intersect the same bag of the
decomposition. In this talk, we will discuss structural properties of
graphs with bounded induced matching treewidth. First, we will show
that graphs with bounded induced matching treewidth that exclude a
fixed biclique as an induced subgraph admit a tree decomposition in
which no bag contains a large independent set. Second, we will show
that classes of graphs with bounded induced matching treewidth and
bounded clique number have bounded chromatic number. These results
prove two recent conjectures of Lima, Milanič, Muršič, Okrasa,
Rzążewski, and Štorgel.

		----------------------------------

Anyone wishing to be added to or removed from the mailing list should
contact Paul Seymour (pds@math.princeton.edu)