Chicago Journal of Theoretical Computer Science

CJTCS Special Issue: CATS 2010

Selected papers from

2010 Computing: The Australasian Theory Symposium

held in Brisbane, Australia, January 18-21 2010.

Guest Editors: Taso Viglas, University of Sydney, Australia

Alex Potanin, Victoria University, Wellington, NZ

Article 2011-2

Published by the Department of Computer Science, The University of Chicago.

k-Cographs are Kruskalian

Ling-Ju Hung
Department of Computer Science and Information Engineering
National Chung Cheng University
168, University Rd., Min-Hsiung
Ton Kloks

May 6, 2011

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 W_1,W_2 of W into nonempty subsets such that either no vertex of W_1 is adjacent to a vertex of W_2 or, such that there exists a permutation pi of k elements such that vertices with color i in W_1 are adjacent exactly to the vertices with color pi(i) in W_2, for all i in {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.

DOI: 10.4086/cjtcs.2011.002

[] 2011, Article 3 [] 2011 Article 1
[back] Special Issue [back] Published articles
[CJCTS home]