Please enable JavaScript.
Coggle requires JavaScript to display documents.
CHROMATIC NUMBER - Coggle Diagram
CHROMATIC NUMBER
Upper Bound
If is connected
Use the brooks theorem
Else if has High degree of Symmetry
Use the maximum degree
Else if sparse or has low degeneracy and low symmetry
If the clique number is bigger than the degree
Use the brokenbosh algorithm
Else
Greedy algorithm
Exact Chromatic Number
If is bibartite
Specific algorithm
Else if is connected
Keep the order as chromatic number
Else
backTracking(Starts from lower bound and reaches the upperbound)
Lower Bound
If is Cyclic
Keep the girth value
Else if has High Degeneracy
Specific algorithm
Else
Use clique algorithm