|
gptkbp:instanceOf
|
graph
|
|
gptkbp:appliesTo
|
planar graphs
undirected graphs
simple graphs
|
|
gptkbp:chromatic_number_of_bipartite_graph
|
2
|
|
gptkbp:chromatic_number_of_complete_graph_K_n
|
n
|
|
gptkbp:chromatic_number_of_cycle_graph_C_n_(n_even)
|
2
|
|
gptkbp:chromatic_number_of_cycle_graph_C_n_(n_odd)
|
3
|
|
gptkbp:chromatic_number_of_empty_graph
|
1
|
|
gptkbp:chromatic_number_of_planar_graph
|
at most 4
|
|
gptkbp:definedIn
|
the minimum number of colors needed to color the vertices of a graph so that no two adjacent vertices share the same color
|
|
gptkbp:field
|
gptkb:mathematics
graph theory
|
|
https://www.w3.org/2000/01/rdf-schema#label
|
Chromatic Number
|
|
gptkbp:introduced
|
gptkb:Francis_Guthrie
|
|
gptkbp:maximumCategory
|
number of vertices in the graph
|
|
gptkbp:minimum_value
|
1
|
|
gptkbp:NP-hard
|
true
|
|
gptkbp:relatedTo
|
gptkb:Four_Color_Theorem
gptkb:Brooks'_theorem
clique number
vertex coloring
chromatic polynomial
chromatic index
|
|
gptkbp:studiedBy
|
discrete mathematics
theoretical computer science
|
|
gptkbp:symbol
|
χ(G)
|
|
gptkbp:used_in
|
scheduling
register allocation
frequency assignment
map coloring
|
|
gptkbp:bfsParent
|
gptkb:Karp's_21_NP-complete_problems
gptkb:Reducibility_Among_Combinatorial_Problems_(Karp,_1972)
|
|
gptkbp:bfsLayer
|
6
|