Max point-tolerance graphs

详细信息    查看全文

• 作者：Daniele Catanzaro^a ; Steven Chaplick^b ; ^{chaplick@math.tu-berlin.de} ; Stefan Felsner^b ; Bjarni V. Halldó ; rsson^c ; Magnú ; s M. Halldó ; rsson^d ; Thomas Hixon^b ; Juraj Stacho^e
• 关键词：Tolerance graphs ; Interval graphs ; L-graphs ; Rectangle intersection graphs ; Outerplanar graphs ; Weighted independent set ; Coloring ; Clique cover
• 刊名：Discrete Applied Mathematics
• 出版年：2017
• 出版时间：10 January 2017
• 年：2017
• 卷：216
• 期：part_P1
• 页码：84-97
• 全文大小：534 K
• 卷排序：216

文摘

A graph GG is a max point-tolerance (MPT)   graph if each vertex vv of GG can be mapped to a pointed-interval  (Iv,pv)(Iv,pv) where IvIv is an interval of RR and pv∈Ivpv∈Iv such that uvuv is an edge of GG iff Iu∩Iv⊇{pu,pv}Iu∩Iv⊇{pu,pv}. MPT graphs model relationships among DNA fragments in genome-wide association studies as well as basic transmission problems in telecommunications. We formally introduce this graph class, characterize it, study combinatorial optimization problems on it, and relate it to several well known graph classes. We characterize MPT graphs as a special case of several 2D geometric intersection graphs; namely, triangle, rectangle, L-shape, and line segment intersection graphs. We further characterize MPT as having certain linear orders on their vertex set. Our last characterization is that MPT graphs are precisely obtained by intersecting special pairs of interval graphs. We also show that, on MPT graphs, the maximum weight independent set problem can be solved in polynomial time, the coloring problem is NP-complete, and the clique cover problem has a 2-approximation. Finally, we demonstrate several connections to known graph classes; e.g., MPT graphs strictly contain interval graphs and outerplanar graphs, but are incomparable to permutation, chordal, and planar graphs.