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,
, constructs a new graph with nodes and edges.The construction is as follows:
Let
. Construct another vertex set and a vertex,w
. Construct a new graph,M
, with vertices . For edges, add edges , and to M. Finally, for all vertices , add edge 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.