DSATUR

For a given approximate coloring algorithm a graph is said to be slightly hard-to-color (SHC) if some implementation of the algorithm uses more colors than the chromatic number. Similarly, a graph is said to be hard-to-color (HC) if every implementation of the algorithm results in a non-optimal coloring. In the paper, we study the smallest of such graphs for the DSATUR vertex coloring algorithm.

Keywords for this software

Anything in here will be replaced on browsers that support the canvas element

References in zbMATH (referenced in 8 articles , 1 standard article )

Showing results 1 to 8 of 8.
Sorted by year (citations)

  1. Sant’Ana da Silva, Eduardo; Pedrini, Helio: Vertex coloring of a graph for memory constrained scenarios (2020)
  2. Cao, Li; Cheng, Hao; Xu, Zhong: An application of a new hybrid genetic algorithm to graph coloring (2007)
  3. Méndez-Díaz, Isabel; Zabala, Paula: A branch-and-cut algorithm for graph coloring (2006)
  4. Satratzemi, Maya: Heuristic algorithms for graph set coloring problem (2006)
  5. Caramia, Massimiliano; Dell’Olmo, Paolo: Bounding vertex coloring by truncated multistage branch and bound (2004)
  6. Jaam, J. M.; Hasnah, A. M.: Improvement of the DSATUR algorithm for graph coloring (2003)
  7. Murphey, Robert A.: Frequency assignment for very large, sparse networks (2002)
  8. Janczewski, R.; Kubale, M.; Manuszewski, K.; Piwakowski, K.: The smallest hard-to-color graph for algorithm DSATUR (2001)