Quasi-threshold graph

In graph-theoretic mathematics, a quasi-threshold graph is a graph that can be constructed using the following rules:
#"K"₁ is a quasi-threshold graph
#If "G" is a quasi-threshold graph, then so is the graph obtained by adding a new vertex connected to every vertex in "G".
#The disjoint union of two quasi-threshold graphs is a quasi-threshold graph.

This class of graphs was first studied by harvtxt|Wolk|1962 in the context of finding a characterization of comparability graphs.

Definition and characterization

Quasi-threshold graphs can be characterized in the following ways: [harvtxt|Wolk|1962; harvtxt|Wolk|1965; harvtxt|Yan|Chen|Chang|1996]

*They are the graphs such that for every path on four vertices "(x₁,x₂,x₃,x₄)" there is either an edge between "x₁" and "x₃" or "x₂" and "x₄" or both.

*They are the graphs that have no induced "P"₄ and no induced "C"₄.

*They are the comparability graphs of arborescence orders.

*They are the graphs that are both cographs and chordal.

*They are the graphs that are both cographs and interval graphs.

Algorithms for recognition

Some of the above characterizations of quasi-threshold directly imply polynomial time recognition algorithms. In particular, cographs, chordal graphs, and interval graphs all have linear time recognition algorithms, so given a graph "G" one can determine whether "G" is either both a cograph and a chordal graph or both a cograph and an interval graph in linear time. harvtxt|Yan|Chen|Chang|1996 note that these algorithms can be complicated, and give a simpler linear time algorithm that exploits the characterization of quasi-threshold graphs as the comparability graphs of arborescence orders. Given an input graph "G", their algorithm either either produces the Hasse diagram for a poset "P" for which "G" is the comparability graph, or returns that "G" is not a quasi-threshold graph.

Relation to other graph classes

uperclasses

The following families of graphs are proper superclasses of the quasi-threshold graphs:

*interval graphs

*chordal graphs

*cographs

ubclasses

The following families of graphs are proper subclasses of the quasi-threshold graphs:

*threshold graphs

Notes

References

* citation
last = Wolk | first = E. S.
title = The comparability graph of a tree
journal = Proceedings of the American Mathematical Society
volume = 13 | year = 1962 | number = 5 | pages = 789-795
url = http://www.jstor.org/stable/2034179.

* citation
last = Wolk | first = E. S.
title = A note on "the comparability graph of a tree"
journal = Proceedings of the American Mathematical Society
volume = 16 | year = 1965 | number = 1 | pages = 17-20
url = http://www.jstor.org/stable/2033992.

* citation
last1 = Yan | first1 = Jing-Ho
last2 = Chen | first2 = Jer-Jeong
last3 = Chang | first3 = Gerard J.
title = Quasi-threshold graphs
journal = Discrete Applied Mathematics
volume = 69 | year = 1996 | issue = 3 | pages = 247–255
doi = 10.1016/0166-218X(96)00094-7.

External links

* cite web
url = http://wwwteo.informatik.uni-rostock.de/isgci/classes/gc_781.html
title = quasi-threshold graph
work = [http://wwwteo.informatik.uni-rostock.de/isgci/index.html Information System on Graph Class Inclusions]