Bichain graphs: Geometric model and universal graphs

详细信息    查看全文

• 作者：Robert Brignall^a ; ^{r.brignall@open.ac.uk" class="auth_mail" title="E-mail the corresponding author} ; Vadim V. Lozin^b ; ^{V.Lozin@warwick.ac.uk" class="auth_mail" title="E-mail the corresponding author} ; ^{v.lozin@warwick.ac.uk" class="auth_mail" title="E-mail the corresponding author} ; Juraj Stacho^b ; ¹ ; ^{stacho@cs.toronto.edu" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Intersection graph ; Universal graph ; Split permutation graph
• 刊名：Discrete Applied Mathematics
• 出版年：2016
• 出版时间：30 January 2016
• 年：2016
• 卷：199
• 期：Complete
• 页码：16-29
• 全文大小：599 K

文摘

Bichain graphs form a bipartite analog of split permutation graphs, also known as split graphs of Dilworth number 2. Unlike graphs of Dilworth number 1 that enjoy many nice properties, split permutation graphs are substantially more complex. To better understand the global structure of split permutation graphs, in the present paper we study their bipartite analog. We show that bichain graphs admit a simple geometric representation and have a universal element of quadratic order, i.e. an X14003837&_mathId=si1069.gif&_user=111111111&_pii=S0166218X14003837&_rdoc=1&_issn=0166218X&md5=45a91d949d2524806f3fbbcf32838c18" title="Click to view the MathML source">nmi>nmi>-universal bichain graph with 14289741b5ace10dc817" title="Click to view the MathML source">n²mi>nmi>2 vertices. The latter result improves a recent cubic construction of universal split permutation graphs.