Nick Brettell, On the graph width parameter mim-width

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.

IBS 이산수학그룹 Discrete Mathematics Group
기초과학연구원 수리및계산과학연구단 이산수학그룹
대전 유성구 엑스포로 55 (우) 34126
IBS Discrete Mathematics Group (DIMAG)
Institute for Basic Science (IBS)
55 Expo-ro Yuseong-gu Daejeon 34126 South Korea
E-mail:, Fax: +82-42-878-9209
Copyright © IBS 2018. All rights reserved.