graph_culberson_flat: Generates a 3-GCP instance following the Culberson's Graph...
In caranha/EvoGCP: Evolutionary Computation Tools for the Graph Coloring Problem

Description Usage Arguments Details Value Examples

Implemented methods: 1. Flat graph 2. Equipartite graph with independent random edge assignment 3. K-Colorable graph with variability and independent random edge assignment

1	graph_culberson_flat(N, probability = 1, flatness = 0)

`N`	Integer - number of vertices in the graph.
`probability`	0..1 - edge's probability.
`flatness`	0.. - (flatness = 0 -> fairly uniform)
`K`	- number of partitions (colors)

Flat Graph Source: http://webdocs.cs.ualberta.ca/~joe/Coloring/Generators/flat.html

The algorithm is defined in 3 steps:

1- Create a permutation of nodes 2- Create 3 groups with N/3 nodes 3- Given two groups A and B, select edges at random from the pairs AxB, subject to: - for any a in A degree(a in AxB) <= ceil(e_AB / |A|) + flatness - for any b in B degree(b in AxB) <= ceil(e_AB / |B|) + flatness - where e_AB = |A|*|B|*(edge's probability)

Discussion about this graph: J. Culberson, F. Luo. “Exploring the k-Colorable landscape with iterated greedy.” Cliques, Coloring, and Satisfiability DIMACS Series in Discrete Mathematics and Theoretical Computer Science, Jan. 1996, pp. 245–284.

a list with two elements: V - number of nodes in the graph, and E - an edge list in the shape of a 2xE matrix. The graph is guaranteed to have a valid 3-coloring