Strong branchwidth and local transversals

DOI10.1016/J.DAM.2004.01.017MaRDI QIDQ1764812zbMATH OpenOpenAlexFDO

Authors Zsolt Tuza

Publication date 22 February 2005

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2004.01.017

zbMATH Keywords

chordal graphsclique numbertrees

Mathematics Subject Classification ID

Trees (05C05) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Structural characterization of families of graphs (05C75) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10)

Review text

It is well known that a graph is chordal (i.e., contains no induced cycles of length greater than three) if and only if it is the vertex-intersection graph of subtrees of a tree [see, e.g., \textit{F. Gavril}, J. Comb. Theory, Ser. B 16, 47--56 (1974; Zbl 0266.05101)]. In this paper a more restricted version called strong branch representation is introduced and concerns representations of chordal graphs as edge intersection graphs of subtrees in a tree of maximum degree 3. This yields a new invariant called strong branchwidth (sbw). Among others, the author characterizes the chordal graphs whose sbw is smaller than their clique number.

Recommendations

• Branchwidth of chordal graphs
• Intersection models of weakly chordal graphs
• Algorithms – ESA 2005
• Finding Intersection Models of Weakly Chordal Graphs
• Edge-maximal graphs of branchwidth k: The k-branches

Cites work

• A characterisation of rigid circuit graphs
• Graph Classes: A Survey
• Graph minors. X: Obstructions to tree-decomposition
• Graphs with Branchwidth at Most Three
• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• On rigid circuit graphs
• The intersection graphs of subtrees in trees are exactly the chordal graphs
• Treewidth. Computations and approximations

Cited in

(5)

• Edge-maximal graphs of branchwidth k: The k-branches
• Intersection models of weakly chordal graphs
• Transchordal graphs
• Edge-maximal graphs of branchwidth k
• Finding Intersection Models of Weakly Chordal Graphs

This page was built for publication: Strong branchwidth and local transversals

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1764812)