Warning

This documents an unmaintained version of NetworkX. Please upgrade to a maintained version and see the current NetworkX documentation.

networkx.generators.mycielski.mycielskian

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.