# 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.

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.