Independence and domination in polygon graphs (Q686246)

Polygon graphs are the intersection graphs of chords inside a convex \(k\)- polygon for some integer \(k\). This class of graphs generalizes permutation graphs and is a subclass of circle graphs. The problems maximum \(r\)-colorable subgraph and minimum dominating set are known to be \(NP\)-complete on circle graphs. The main results of this paper are polynomial time algorithms for these problems on \(k\)-polygon graphs with fixed \(k\).