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
References in zbMATH (referenced in 7 articles , 1 standard article )
Showing results 1 to 7 of 7.
- Cao, Li; Cheng, Hao; Xu, Zhong: An application of a new hybrid genetic algorithm to graph coloring (2007)
- Méndez-Díaz, Isabel; Zabala, Paula: A branch-and-cut algorithm for graph coloring (2006)
- Satratzemi, Maya: Heuristic algorithms for graph set coloring problem (2006)
- Caramia, Massimiliano; Dell’Olmo, Paolo: Bounding vertex coloring by truncated multistage branch and bound (2004)
- Jaam, J. M.; Hasnah, A. M.: Improvement of the DSATUR algorithm for graph coloring (2003)
- Murphey, Robert A.: Frequency assignment for very large, sparse networks (2002)
- Janczewski, R.; Kubale, M.; Manuszewski, K.; Piwakowski, K.: The smallest hard-to-color graph for algorithm DSATUR (2001)