Heuristic Ordering Strategies
A commonly used ordering for greedy coloring is to choose a vertex v of minimum degree, order the remaining vertices, and then place v last in the ordering. If every subgraph of a graph G contains a vertex of degree at most d, then the greedy coloring for this ordering will use at most d + 1 colors. The smallest such d is commonly known as the degeneracy of the graph.
For a graph of maximum degree Δ, any greedy coloring will use at most Δ + 1 colors. Brooks' theorem states that with two exceptions (cliques and odd cycles) at most Δ colors are needed. One proof of Brooks' theorem involves finding a vertex ordering in which the first two vertices are adjacent to the final vertex but not adjacent to each other, and each subsequent vertex has at least one earlier neighbor. For an ordering with this property, the greedy coloring algorithm uses at most Δ colors.
Read more about this topic: Greedy Coloring
Famous quotes containing the words ordering and/or strategies:
“Our goal as a parent is to give life to our children’s learning—to instruct, to teach, to help them develop self-discipline—an ordering of the self from the inside, not imposition from the outside. Any technique that does not give life to a child’s learning and leave a child’s dignity intact cannot be called discipline—it is punishment, no matter what language it is clothed in.”
—Barbara Coloroso (20th century)
“By intervening in the Vietnamese struggle the United States was attempting to fit its global strategies into a world of hillocks and hamlets, to reduce its majestic concerns for the containment of communism and the security of the Free World to a dimension where governments rose and fell as a result of arguments between two colonels’ wives.”
—Frances Fitzgerald (b. 1940)