Back to Search Start Over

Quasi-tree-partitions of graphs with an excluded subgraph

Authors :
Liu, Chun-Hung
Wood, David R.
Publication Year :
2024

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.

Subjects

Subjects :
Mathematics - Combinatorics

Details

Database :
arXiv
Publication Type :
Report
Accession number :
edsarx.2408.00983
Document Type :
Working Paper