#

### 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

Taiwan

`hunglc@cs.ccu.edu.tw`,

and

Ton Kloks

*May 6, 2011*
##### Abstract

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.

- The article:
**PDF** (188,029 bytes)
- Source material:
**ZIP** (51,015 bytes)
- Self citation in
**BIBTeX** (256 bytes)

2011, Article 3
2011 Article 1

Special Issue
Published articles