graph_coloring: Graph Coloring over Adjacency List
In saurfang/graphcoloring: Graph Coloring Algorithms for Tidygraph

Description Usage Arguments Details Functions References See Also Examples

These functions perform graph coloring using various algorithms over an adjacency list.

In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices of a graph such that no two adjacent vertices share the same color; this is called a vertex coloring.

graph_coloring_dsatur(adj_list)

graph_coloring_msc(adj_list)

graph_coloring_lmxrlf(adj_list)

graph_coloring_hybrid_dsatur_tabucol(adj_list)

graph_coloring_hybrid_lmxrlf_tabucol(adj_list)

graph_coloring_tabucol(adj_list, k, tabu_size = 25L, rep = 100L, nbmax = 1000L)

`adj_list`	an adjacency list in the format of `list` of `integer` vector. The outer list should enumerate nodes comprehensively and each integer vector enumerates corresponding neighboring nodes
`k`	number of colors to use for graph coloring
`tabu_size`	size of tabu list
`rep`	number of inner iterations
`nbmax`	maximum number of non-improving outer iterations

graph_coloring_hybrid_dsatur_tabucol() and graph_coloring_hybrid_lmxrlf_tabucol() use a hybrid approach to run DSATUR and lmXRLF first to determine an upper bound for the graph chromatic number. It then searches better solutions by running lowered chromatic number through TabuCol to check if the graph can be colored with less colors.

graph_coloring_dsatur: Color graph using DSATUR algorithm \insertCiteBrelaz:1979:NMC:359094.359101graphcoloring
graph_coloring_msc: Color graph using Maximum Cardinality Search(MCS) algorithm \insertCitePalsberg:2007:RAV:1273694.1273695graphcoloring
graph_coloring_lmxrlf: Color graph using Least-constraining Most-constrained eXtended RLF(lmXRLF) algorithm \insertCiteKirovski:1998:ECL:277044.277165graphcoloring
graph_coloring_hybrid_dsatur_tabucol: Color graph using a hybrid of DASTUR and TabuCol algorithm \insertCiteKirovski:1998:ECL:277044.277165,Brelaz:1979:NMC:359094.359101,Hertz:1987:UTS:44141.44146graphcoloring
graph_coloring_hybrid_lmxrlf_tabucol: Color graph using a hybrid of lmXRLF and TabuCol algorithm \insertCiteKirovski:1998:ECL:277044.277165,Hertz:1987:UTS:44141.44146graphcoloring
graph_coloring_tabucol: Color graph using TabuCol algorithm \insertCiteHertz:1987:UTS:44141.44146graphcoloring

https://en.wikipedia.org/wiki/Graph_coloring

https://github.com/brrcrites/GraphColoring

\insertRef

Brelaz:1979:NMC:359094.359101graphcoloring

\insertRef

Palsberg:2007:RAV:1273694.1273695graphcoloring

\insertRef

Kirovski:1998:ECL:277044.277165graphcoloring

\insertRef

Hertz:1987:UTS:44141.44146graphcoloring

color_graph()

library(tidygraph)

if (requireNamespace("sf", quietly = TRUE) && requireNamespace("USAboundaries", quietly = TRUE)) {
 library(sf)
 library(USAboundaries)

 us_states() %>%
   filter(!(name %in% c("Alaska", "District of Columbia", "Hawaii", "Puerto Rico"))) %>%
   transmute(
     color = st_intersects(.) %>%
       graph_coloring_dsatur() %>%
       as.factor()
     ) %>%
   plot()
}