mycielskianGraph Class Reference
[Graph series]

Derived graph with increased chromatic number, but with the same clique number. More...

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

---

Detailed Description

Derived graph with increased chromatic number, but with the same clique number.

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 half-way between the center and the corresponding original node.

---

Constructor & Destructor Documentation

mycielskianGraph (  abstractMixedGraph &  G, TOption  options = 0 )  throw (ERRejected)

Apply the Mycielskian construction to a given graph. Parameters: G  The original graph options  Any combination of OPT_SUB and OPT_MAPPINGS

mycielskianGraph (  unsigned  k, goblinController &  _CT = goblinDefaultContext )  throw (ERRejected)

Recursive application of the Mycielskian construction. Parameters: k  The recursion depth. k=2 denotes the K_2 induction base _CT  The controller to handle this object