#include <sparseGraph.h>
Inheritance diagram for mycielskianGraph:
Public Member Functions  
mycielskianGraph (abstractMixedGraph &G, TOption options=0) throw (ERRejected)  
mycielskianGraph (unsigned k, goblinController &_CT=goblinDefaultContext) throw (ERRejected) 
The derived graph has the original graph and a star graph as induced subgraphs, and both subgraphs are vertex disjoint. Every original node is matched by a leave in the star.
By iterated application of this construction, the duality gap between the chromatic number and the clique number can be made arbitrarily large.
Draw the star nodes as if the original nodes were all on a sphere: The star center node is in the barycenter of the original nodes. The star leave nodes are halfway between the center and the corresponding original node.

Apply the Mycielskian construction to a given graph.


Recursive application of the Mycielskian construction.
