A class of graphs is Kruskalian if Kruskal’s theorem on a well-quasi-ordering of finite trees provides a finite characterization in terms of forbidden induced subgraphs.
Let k be a natural number. A graph is a k-cograph if its vertices can be colored with colors from the set {1,...,k} such that for every nontrivial subset of vertices W there exists a partition {W1,W2} into nonempty subsets such that either no vertex of W1 is adjacent to a vertex of W2 or, such that there exists a permutation π ∈ Sk such that vertices with color i in W1 are adjacent exactly to the vertices with color π(i) in W2, for all i ∈ {1,...,k}. We prove that k-cographs are Kruskalian. We show that k-cographs have bounded rankwidth and that they can be recognized in O(n^3) time.
Cite as: Hung, L.-J. and Kloks, T. (2010). Kruskalian Graphs. In Proc. 16-th Computing: The Australasian Theory Symposium (CATS 2010) Brisbane, Australia. CRPIT, 109. Viglas, T. and Potanin, A. Eds., ACS. 49-54
(from crpit.com)
(local if available)