|
gptkbp:instanceOf
|
mathematical optimization
|
|
gptkbp:application
|
scheduling
register allocation
frequency assignment
|
|
gptkbp:complexity
|
gptkb:NP-hard
|
|
gptkbp:defines
|
Assigning colors to elements of a graph subject to certain constraints
|
|
gptkbp:field
|
gptkb:mathematics
computer science
graph theory
|
|
gptkbp:generalizes
|
map coloring problem
|
|
gptkbp:hasVariant
|
edge coloring
list coloring
acyclic coloring
distance coloring
face coloring
total coloring
|
|
https://www.w3.org/2000/01/rdf-schema#label
|
Graph coloring problem
|
|
gptkbp:introducedIn
|
19th century
|
|
gptkbp:notable_for
|
gptkb:Four_color_theorem
gptkb:Vizing's_theorem
gptkb:Brooks'_theorem
|
|
gptkbp:numberOfIssues
|
gptkb:Hadwiger's_conjecture
gptkb:Erdős–Faber–Lovász_conjecture
gptkb:Reed's_conjecture
gptkb:Total_coloring_conjecture
|
|
gptkbp:parameter
|
gptkb:university
chromatic number
clique number
girth
chromatic index
|
|
gptkbp:prohibits
|
No two adjacent vertices share the same color
|
|
gptkbp:relatedTo
|
gptkb:planar_graph
edge coloring
chromatic number
vertex coloring
NP-complete problem
|
|
gptkbp:solvedBy
|
heuristics
backtracking
greedy algorithm
|
|
gptkbp:studiedBy
|
gptkb:Paul_Erdős
gptkb:Wolfgang_Haken
gptkb:Kenneth_Appel
gptkb:Alfred_Kempe
gptkb:Heinrich_Heesch
|
|
gptkbp:usedIn
|
resource allocation
network design
pattern matching
|
|
gptkbp:bfsParent
|
gptkb:NP-completeness
|
|
gptkbp:bfsLayer
|
5
|