Extending Partial Representations of Unit Circular-arc Graphs

2017/06/03 by Zeman, Peter
#Discrete Mathematics (cs.DM) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.1706.00928

Abstract

The partial representation extension problem, introduced by Klavík et al. (2011), generalizes the recognition problem. In this short note we show that this problem is NP-complete for unit circular-arc graphs.

Related

• Extending Partial Representations of Circular-Arc Graphs
• Bounded, minimal, and short representations of unit interval and unit circular-arc graphs
• Extending Partial Representations of Circle Graphs
• Characterization of Chordal Circular-arc Graphs: I. Split Graphs
• Extending Partial Representations of Proper and Unit Interval Graphs