The search for minimal edge $1$-extension of an undirected colored graph

P. V. Razumovsky

Izvestiya of Saratov University. Mathematics. Mechanics. Informatics, Tome 21 (2021) no. 3, pp. 400-407

Résumé

Let $G=(V, \alpha, f)$ be a colored graph with a coloring function $f$ defined on its vertices set $V$. Colored graph $G^*$ is an edge $1$-extension of a colored graph $G$ if $G$ could be included into each subgraph taking into consideration the colors. These subgraphs could be built from $G^*$ by removing one of the graph's edges. Let colored edge $1$-extension $G^*$ be minimal if $G^*$ has as many vertices as the original graph $G$ and it has the minimal number of edges among all edge $1$-extensions of graph $G$. The article considers the problem of search for minimal edge $1$-extensions of a colored graph with isomorphism rejection technique. The search algorithm of all non-isomorphic minimal edge $1$-extensions of a defined colored graph is suggested.