Forbidden induced subgraphs of normal Helly circular-arc graphs: Characterization and detection

详细信息    查看全文

• 作者：Yixin Cao^a ; ^{yixin.cao@polyu.edu.hk} ; Luciano N. Grippo^b ; ^{lgrippo@ungs.edu.ar} ; Martí ; n D. Safe^b ; ^{msafe@ungs.edu.ar}
• 关键词：Certifying algorithms ; Linear-time ; (proper) interval graphs ; Chordal graphs ; (minimal) forbidden induced subgraphs ; Holes ; (normal ; Helly ; proper) circular-arc models
• 刊名：Discrete Applied Mathematics
• 出版年：2017
• 出版时间：10 January 2017
• 年：2017
• 卷：216
• 期：part_P1
• 页码：67-83
• 全文大小：1187 K
• 卷排序：216

文摘

A normal Helly circular-arc graph is the intersection graph of a set of arcs on a circle of which no three or less arcs cover the whole circle. Lin et al. (2013) characterized circular-arc graphs that are not normal Helly circular-arc graphs, and used them to develop the first recognition algorithm for this graph class. As open problems, they ask for the forbidden subgraph characterization and a direct recognition algorithm for normal Helly circular-arc graphs, both of which are resolved by the current paper. Moreover, when the input is not a normal Helly circular-arc graph, our recognition algorithm finds in linear time a minimal forbidden induced subgraph as a certificate. Our approach yields also a considerably simpler algorithm for the certifying recognition of proper Helly circular-arc graphs, a subclass of normal Helly circular-arc graphs.