Clique trees of infinite locally finite chordal graphs

MaRDI QIDQ1753106zbMATH OpenFDO

Authors Christoph Hofer-Temmel, Florian Lehner

Publication date 25 May 2018

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1311.7001, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v25i2p9

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

chordal graphsclique treesgraph theoryinfinite graphs

Mathematics Subject Classification ID

Trees (05C05) Enumeration in graph theory (05C30) Graph representations (geometric and intersection representations, etc.) (05C62)

Abstract: We investigate clique trees of infinite locally finite chordal graphs. Our main contribution is a bijection between the set of clique trees and the product of local finite families of finite trees. Even more, the edges of a clique tree are in bijection with the edges of the corresponding collection of finite trees. This allows us to enumerate the clique trees of a chordal graph and extend various classic characterisations of clique trees to the infinite setting.

Review text

Summary: We investigate clique trees of infinite locally finite chordal graphs. Our main contribution is a bijection between the set of clique trees and the product of local finite families of finite trees. Even more, the edges of a clique tree are in bijection with the edges of the corresponding collection of finite trees. This allows us to enumerate the clique trees of a chordal graph and extend various classic characterisations of clique trees to the infinite setting.

Recommendations

• scientific article; zbMATH DE number 554762
• Clique tree generalization and new subclasses of chordal graphs
• scientific article; zbMATH DE number 2170436
• On the tree representation of chordal graphs
• Clique trees of chordal graphs: leafage and 3-asteroidals

Cites work

• Counting clique trees and computing perfect elimination schemes in parallel
• scientific article; zbMATH DE number 554762 (Why is no real title available?)
• scientific article; zbMATH DE number 2203240 (Why is no real title available?)
• On rigid circuit graphs
• On the Desirability of Acyclic Database Schemes
• On the representation of triangulation graphs in trees
• Power of Natural Semijoins
• The intersection graphs of subtrees in trees are exactly the chordal graphs

Cited in

(1)

• Shearer's point process, the hard-sphere model, and a continuum Lovász local lemma

This page was built for publication: Clique trees of infinite locally finite chordal graphs

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