graphscope.nx.generators.mycielski.mycielskian

graphscope.nx.generators.mycielski.mycielskian(G, iterations=1)

Returns the Mycielskian of a simple, undirected graph G

The Mycielskian of graph preserves a graph’s triangle free property while increasing the chromatic number by 1.

The Mycielski Operation on a graph, $G=(V,E)$, constructs a new graph with $2|V|+1$ nodes and $3|E|+|V|$ edges.

The construction is as follows:

Let $V=0,...,n-1$. Construct another vertex set $U=n,...,2n$ and a vertex, w. Construct a new graph, M, with vertices $U\bigcup V\bigcup w$. For edges, $(u,v)\in E$ add edges $(u,v),(u,v+n)$, and $(u+n,v)$ to M. Finally, for all vertices $u\in U$, add edge $(u,w)$ to M.

The Mycielski Operation can be done multiple times by repeating the above process iteratively.

More information can be found at https://en.wikipedia.org/wiki/Mycielskian

Parameters:

• G (graph) – A simple, undirected NetworkX graph

• iterations (int) – The number of iterations of the Mycielski operation to perform on G. Defaults to 1. Must be a non-negative integer.

Returns:

M – The Mycielskian of G after the specified number of iterations.

Return type:

graph

Notes

Graph, node, and edge data are not necessarily propagated to the new graph.