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)[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: 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. M – The Mycielskian of G after the specified number of iterations. graph

Notes

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