Editing Graph coloring (section)

=== Polynomial time ===
Determining if a graph can be colored with 2 colors is equivalent to determining whether or not the graph is [[Bipartite graph|bipartite]], and thus computable in [[linear time]] using [[breadth-first search]] or [[depth-first search]]. More generally, the chromatic number and a corresponding coloring of  [[perfect graph]]s can be computed in [[polynomial time]] using [[semidefinite programming]]. [[Closed-form expression|Closed formulas]] for chromatic polynomials are known for many classes of graphs, such as forests, chordal graphs, cycles, wheels, and ladders, so these can be evaluated in polynomial time.

If the graph is planar and has low branch-width (or is nonplanar but with a known [[branch-decomposition]]), then it can be solved in polynomial time using dynamic programming. In general, the time required is polynomial in the graph size, but exponential in the branch-width.