mycielskian#

mycielskian(G, iterations=1)[source]#

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:

Ggraph

A simple, undirected NetworkX graph

iterationsint

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

Returns:

Mgraph

The Mycielskian of G after the specified number of iterations.

Notes

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