Graph product structure theory describes how graphs in some complex classes can be represented as subgraphs of products of simpler, tree-like graphs. Since 2019, there has been a surge of interest in this field following the discovery that every planar graph is contained in the product of a tree-like graph and a path. This result opened up a new research direction and has been the key tool in solving several longstanding open problems. These lecture notes will introduce graph product structure theory and provide the tools necessary to understand the theory and the proof for planar graphs.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Graph Product Structure Theory with Applications

  • Vida Dujmović

摘要

Graph product structure theory describes how graphs in some complex classes can be represented as subgraphs of products of simpler, tree-like graphs. Since 2019, there has been a surge of interest in this field following the discovery that every planar graph is contained in the product of a tree-like graph and a path. This result opened up a new research direction and has been the key tool in solving several longstanding open problems. These lecture notes will introduce graph product structure theory and provide the tools necessary to understand the theory and the proof for planar graphs.