Ferrers dimension of grid intersection graphs

详细信息    查看全文

• 作者：Steven Chaplick^a ; ^{chaplick@math.tu-berlin.de} ; Pavol Hell^b ; ^pavol@sfu.ca ; Yota Otachi^c ; ^{otachi@jaist.ac.jp} ; Toshiki Saitoh^d ; ^{saitoh@eedept.kobe-u.ac.jp} ; Ryuhei Uehara^c ; ^{uehara@jaist.ac.jp}
• 关键词：Ferrers dimension ; Boxicity ; Segment-ray graph ; Unit grid intersection graph
• 刊名：Discrete Applied Mathematics
• 出版年：2017
• 出版时间：10 January 2017
• 年：2017
• 卷：216
• 期：part_P1
• 页码：130-135
• 全文大小：410 K
• 卷排序：216

文摘

We investigate the Ferrers dimension of classes of grid intersection graphs and show properties and characterizations. In particular, we show that (1) the grid intersection graphs form a proper subclass of the class of bipartite graphs of Ferrers dimension 4, (2) segment-ray graphs have a forbidden submatrix characterization, and (3) a bipartite graph is a unit grid intersection graph if and only if it is the intersection of two bipartite permutation graphs.