Class ChromaticNumber


  • public abstract class ChromaticNumber
    extends java.lang.Object
    Allows the chromatic number of a graph to be calculated. This is the minimal number of colors needed to color each vertex such that no two adjacent vertices share the same color. This algorithm will not find the true chromatic number, since this is an NP-complete problem. So, a greedy algorithm will find an approximate chromatic number.
    Since:
    Dec 21, 2008
    Author:
    Andrew Newell
    • Constructor Summary

      Constructors 
      Constructor Description
      ChromaticNumber()  
    • Method Summary

      All Methods Static Methods Concrete Methods 
      Modifier and Type Method Description
      static <V,​E>
      int
      findGreedyChromaticNumber​(UndirectedGraph<V,​E> g)
      Finds the number of colors required for a greedy coloring of the graph.
      • Methods inherited from class java.lang.Object

        clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
    • Constructor Detail

      • ChromaticNumber

        public ChromaticNumber()
    • Method Detail

      • findGreedyChromaticNumber

        public static <V,​E> int findGreedyChromaticNumber​(UndirectedGraph<V,​E> g)
        Finds the number of colors required for a greedy coloring of the graph.
        Parameters:
        g - an undirected graph to find the chromatic number of
        Returns:
        integer the approximate chromatic number from the greedy algorithm