Characterizing graphs of maximum matching width at most 2

Jisu Jeong*, Seongmin Ok, Geewon Suh

*Corresponding author for this work

Research output: Contribution to journalJournal article

331 Downloads (Pure)

Abstract

The maximum matching width is a width-parameter that is de ned on a branch-decomposition over the vertex set of a graph. The size of a maximum matching in the bipartite graph is used as a cut-function. In this paper, we characterize the graphs of maximum matching width at most 2 using the minor obstruction set. Also, we compute the exact value of the maximum matching width of a grid.
Original languageEnglish
JournalDiscrete Applied Mathematics
Volume248
Pages (from-to)102-113
ISSN0166-218X
DOIs
Publication statusPublished - 2017

Keywords

  • Maximum matched width
  • Minor obstructions
  • Grid

Fingerprint Dive into the research topics of 'Characterizing graphs of maximum matching width at most 2'. Together they form a unique fingerprint.

Cite this