Module mycielskian 

Mycielski construction (ALGO-CN-019).

Counterpart of igraph_mycielskian() and igraph_mycielski_graph() in references/igraph/src/constructors/mycielskian.c:97-244.

The Mycielski construction M(G) takes a graph G on n vertices and m edges and produces a larger graph with 2n + 1 vertices and 3m + n edges that increases the chromatic number by one while preserving the triangle-free property.

Per iteration, label the original vertices v_0..v_{n-1} and add:

• n shadow vertices u_0..u_{n-1}, where u_i is connected to every original neighbour of v_i (so for each (v_i, v_j) in G we emit (v_i, u_j) and (v_j, u_i));
• a single apex vertex w connected to every u_i.

Two corner cases are folded inline so iterative chains stay connected: the null graph (vcount = 0) consumes one k step by becoming the singleton, and the singleton (vcount = 1) consumes one k step by becoming the two-path P_2. After those reductions the loop runs the literal recurrence vcount' = 2*vcount + 1, ecount' = 3*ecount + vcount.

The canonical Mycielski graphs M_k are produced by mycielski_graph: M_0 = null, M_1 = singleton, M_2 = P_2, M_3 = C_5, M_4 = Grötzsch graph (11 vertices, 20 edges, triangle-free, chromatic number 4).

Time complexity: O(|V| · 2^k + |E| · 3^k).

Functions

mycielski_graph

Construct the canonical Mycielski graph M_k.

mycielskian

Apply k Mycielski iterations to graph.