Several notions of rank-width for countable graphs

详细信息    查看全文

• 作者：Bruno Courcelle¹ ; ^{courcell@labri.fr}
• 关键词：Rank-width ; Linear rank-width ; Compactness ; Koenig's lemma
• 刊名：Journal of Combinatorial Theory, Series B
• 出版年：2017
• 出版时间：March 2017
• 年：2017
• 卷：123
• 期：Complete
• 页码：186-214
• 全文大小：581 K
• 卷排序：123

文摘

We define several notions of rank-width for countable graphs. We compare, for each of them the width of a countable graph with the least upper bound of the widths of its finite induced subgraphs. A width measure has the compactness property if these two values are equal. One of our notions of rank-width for countable graphs uses quasi-trees (generalized trees where “paths” may have any order type) and has this property. So has linear rank-width, based on arbitrary linear orders. A more natural notion of rank-width based on countable cubic trees (we call it discrete rank-width) has a weaker type of compactness: the corresponding width is at most twice the least upper bound of the widths of the finite induced subgraphs. The notion of discrete linear rank-width, based on discrete linear orders has no compactness property.