Tolerance intersection graphs of degree bounded subtrees of a tree with constant tolerance 2

作者：Cohen Elad^*; Golumbic Martin Charles; Lipshteyn Marina; Stern Michal

来源：Discrete Mathematics, 2017, 340(2): 209-222.

DOI：10.1016/j.disc.2016.08.015

• Chordal graph
• Weakly chordal graph
• Intersection graph of subtrees of a tree
• Complete bipartite graph

An (h, s, t)-representation of a graph G consists of a collection of subtrees {S-nu : nu is an element of V(G)} of a tree T, such that (i) the maximum degree of T is at most h, (ii) every subtree has maximum degree at most s, and (iii) there is an edge between two vertices in the graph if and only if the corresponding subtrees in T have at least t vertices in common. Jamison and Mulder denote the family of graphs that admit such a representation as [h, s, t].
Our main theorem shows that the class of weakly chordal graphs is incomparable with the class [h, s, t]. We introduce new characterizations of the graph K-2,(n) in terms of the families [h, s, 2] and [h, s, 3]. We then present our second main result characterizing the graphs in [4, 3, 2] as being the graphs in [4, 4, 2] avoiding a particular family of substructures, and we give a recognition algorithm for the family [4, 3, 2].

• 出版日期2017-2-6