Quasi-tree-partitions of graphs with an excluded subgraph

2024/08/02 by Liu, Chun-Hung, Wood, David R. · 1 citation
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2408.00983

Abstract

This paper studies the structure of graphs with given tree-width and excluding a fixed complete bipartite subgraph, which generalises the bounded degree setting. We give a new structural description of such graphs in terms of so-called quasi-tree-partitions. We demonstrate the utility of this result through applications to (fractional) clustered colouring. Further generalisations of these structural and colouring results are presented.

Cited by

• Tree decompositions with small width, spread, order and degree

Related

• Tree-Partitions with Small Bounded Degree Trees
• An alternative characterisation of graphs quasi-isometric to graphs of bounded treewidth
• Partitioning a graph into monochromatic connected subgraphs
• Clustered Graph Coloring and Layered Treewidth
• Partitions of Graphs into Special Bipartite Graphs