Graphs of intersections of closed polygonal chains

N. P. Prochorov ; E. N. Dul

Journal of the Belarusian State University. Mathematics and Informatics, Tome 1 (2021), pp. 54-68

Résumé

In the paper such subclass of string graphs as intersection graphs of closed polygonal chains (class of $CPC$-graphs) was considered, necessary conditions for belonging to that class, forbidden subgraphs and operations with graphs which preserve belonging to the $CPC$ class were found. Considered question about the existence of $k$-regular $CPC$-graphs, particularly, pairs $(k, n)$, such that there exists k-regular $CPC$-graph on $n$ vertexes were found, proved that there are infinitely many $k$-regular $CPC$-graphs for any $k\in \mathbb{N}$, estimations for the number of $k$, such that $k$-regular graph on $n$ vertexes exists, were given. Algorithmic questions in the class of $CPC$-graphs were investigated. It was proved that independent and dominating set problems, coloring problem and the problem about maximal cycle are $NP$-hard in the class of $CPC$-graphs, and problem of recognition of the $CPC$-graphs belongs to the $PSPACE$ class.

Détail

Keywords: intersection graph; intersection graph of closed polygonal chains; regular graph; $NP$-completeness; polynomial-time reduction.