首页    期刊浏览 2024年11月27日 星期三
登录注册

文章基本信息

  • 标题:k-Cographs are Kruskalian
  • 本地全文:下载
  • 作者:Ling-Ju Hung ; Ton Kloks.
  • 期刊名称:Chicago Journal of Theoretical Computer Science
  • 印刷版ISSN:1073-0486
  • 出版年度:2011
  • 卷号:2011
  • 出版社:MIT Press ; University of Chicago, Department of Computer Science
  • 摘要:

    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.

国家哲学社会科学文献中心版权所有