Maximum induced matching width, also known as mim-width, is a width parameter for graphs introduced by Vatshelle in 2012. This parameter can be defined over branch decompositions of a graph G, where the width of a vertex partition (X,Y) in G is the size of a maximum induced matching in the bipartite graph induced by edges of G with one endpoint in X and one endpoint in Y. In this talk, I will present a quick overview of mim-width and some key results that highlight why this parameter is of interest from both a theoretical and algorithmic point of view. I will discuss some recent work regarding the boundedness or unboundedness of mim-width for hereditary classes defined by forbidding one or two induced subgraphs, and for generalisations of convex graphs. I will also touch on some interesting applications of this work, in particular for colouring and list-colouring. This is joint work with Jake Horsfield, Andrea Munaro, Giacomo Paesani, and Daniel Paulusma.
기초과학연구원 이산수학그룹