Package org.graph4j.generators

Class MycielskiGenerator

java.lang.Object

org.graph4j.generators.AbstractGraphGenerator

org.graph4j.generators.MycielskiGenerator

public class MycielskiGenerator
extends AbstractGraphGenerator

Generates Mycielski graphs. A Mycielski graph Mk of order k is a triangle-free graph with chromatic number k. Using this construction, Mycielski showed that there exist triangle-free graphs with arbitrarily large chromatic number. M1 is the singleton graph, M2 is the 2-path graph, M3 is the 5-cycle graph.

Author:

Cristian Frăsinaru

Field Summary

Fields inherited from class org.graph4j.generators.AbstractGraphGenerator

vertices

Constructor Summary

Constructors

Constructor	Description
MycielskiGenerator()

Method Summary

Modifier and Type	Method	Description
Graph	create(int chromaticNumber)	Creates a Mycielski graph with the specified chromatic number.
Graph	createFrom(Graph graph, int chromaticNumber)	Creates a Mycielski graph starting from a specified graph.

Methods inherited from class org.graph4j.generators.AbstractGraphGenerator

addRandomEdges

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Details

MycielskiGenerator

public MycielskiGenerator()

Method Details

create

public Graph create(int chromaticNumber)

Creates a Mycielski graph with the specified chromatic number. The resulting graph is triangle-free.

Parameters:

chromaticNumber - the chromatic number of the generated graph.

Returns:

a new triangle-free graph having the chromatic number chromaticNumber + 1.

createFrom

public Graph createFrom(Graph graph,
 int chromaticNumber)

Creates a Mycielski graph starting from a specified graph. The method does not verify if the specified graph is triangle-free and its chromatic number is the specified one.

Parameters:

graph - a triangle-free graph having the specified chromatic number.

chromaticNumber - the chromatic number of graph.

Returns:

a new triangle-free graph having the chromatic number chromaticNumber + 1.