Premium
Chordal graphs, interval graphs, and wqo
Author(s) -
Ding Guoli
Publication year - 1998
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/(sici)1097-0118(199806)28:2<105::aid-jgt4>3.0.co;2-p
Subject(s) - chordal graph , combinatorics , mathematics , interval graph , treewidth , split graph , clique sum , indifference graph , discrete mathematics , block graph , pathwidth , clique , interval (graph theory) , graph , 1 planar graph , line graph
Let precedes, equal to be the induced‐minor relation. It is shown that, for every t , all chordal graphs of clique number at most t are well‐quasi‐ordered by precedes, equal to. On the other hand, if the bound on clique number is dropped, even the class of interval graphs is not well‐quasi‐ordered by precedes, equal to. © 1998 John Wiley & Sons, Inc. J Graph Theory 28: 105–114, 1998