zbMATH — the first resource for mathematics

Edge-maximal graphs of branchwidth \(k\): The \(k\)-branches. (English) Zbl 1229.05153
Summary: Treewidth and branchwidth are two closely related connectivity parameters of graphs. Graphs of treewidth at most \(k\) have well-known alternative characterizations as subgraphs of chordal graphs and as partial \(k\)-trees. In this paper we give analogous alternative characterizations for graphs of branchwidth at most \(k\). We first show that they are the subgraphs of chordal graphs where every maximal clique \(X\) has three subsets of size at most \(k\) each such that any two subsets have union \(X\), with the property that every minimal separator contained in \(X\) is contained in one of the three subsets. Secondly, we give a characterization of the edge-maximal graphs of branchwidth \(k\), that we call \(k\)-branches.

05C35 Extremal problems in graph theory
05C40 Connectivity
05C05 Trees
Full Text: DOI
[1] Arnborg, S.; Proskurowski, A., Recognition of partial \(k\)-trees, Congresus numerantium, 47, 69-75, (1985)
[2] Bodlaender, H., Treewidth: algorithmic techniques and results, (), 19-36 · Zbl 0941.05057
[3] Bodlaender, H.; Thilikos, D., Graphs with branchwidth at most three, Journal of algorithms, 32, 167-194, (1999) · Zbl 0946.68103
[4] Gavril, F., The intersection graphs of subtrees in trees are exactly the chordal graphs, Journal of combinatorial theory series B, 16, 47-56, (1974) · Zbl 0266.05101
[5] Kloks, T.; Kratochvil, J.; Müller, H., New branchwidth territories, (), 173-185 · Zbl 0924.05063
[6] F. Mazoit, Décompositions algorithmiques des graphes, PhD thesis, École Normale Supérieure de Lyon, 2004 (in French)
[7] Paul, C.; Proskurowski, A.; Telle, J.A., Algorithmic generation of graphs of branchwidth \(\leq k\), (), 206-216
[8] Paul, C.; Telle, J.A., Edge-maximal graphs of branchwidth \(k\), (), 363-368 · Zbl 1200.05194
[9] Paul, C.; Telle, J.A., New tools and simple algorithms for branchwidth, (), 379-390 · Zbl 1162.68503
[10] Rose, D., On simple characterization of \(k\)-trees, Discrete mathematics, 7, 317-322, (1974) · Zbl 0285.05128
[11] Robertson, N.; Seymour, P.D., Graph minors X: obstructions to tree-decomposition, Journal on combinatorial theory series B, 52, 153-190, (1991) · Zbl 0764.05069
[12] van Leeuven, J., Graphs algorithms, (), 527-631
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.