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,...,n1. Construct another vertex set U=n,...,2n and a vertex, w. Construct a new graph, M, with vertices UVw. For edges, (u,v)E add edges (u,v),(u,v+n), and (u+n,v) to M. Finally, for all vertices uU, 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.