Ordering for Coloring and MoreAssefaw H. Gebremedhin ∗Arijit Tarafdar †Duc Nguyen

Alex Pothen

Extended Abstract

Consider the distance-1 coloring problem: given a graph, assign positive integers (called colors)to vertices such that every pair of adjacent vertices receives distinct colors and the number of colors
used is minimized. A greedy heuristic for this problem progressively extends a partial coloring byprocessing one vertex at a time, in some order, in each step permanently assigning a vertex thesmallest allowable color. The order in which the vertices are processed determines the number ofcolors used by the algorithm. Three ordering techniques that are known to be fairly effective inpractice are Largest First, Incidence Degree, and Smallest Last.
The definition typically found in the literature for each of these techniques is intertwined withthe coloring algorithm itself. We characterize these in a manner that is independent of a coloringalgorithm, which aids the creation of more modular implementations and makes it easier to findother contexts in which the orderings might be useful. The characterization simply uses the notionsof back and forward degree. In an ordering π = {v1 , v2 , . . . , vn } of the vertices of a graph G, theback degree of the vertex vi is the number of neighbors of vi ordered before vi in π, and the forward
degree of vi is the number of neighbors of vi ordered after vi in π. Clearly, the degree of vi is thesum of its back degree and forward degree. Our characterization is summarized in Table 1. The
third item in the table, Dynamic Largest First, is a new ordering technique we developed and foundto be especially effective for a specialized coloring problem to be discussed later.
The ordering variants LF, ID, and DLF are defined left-to-right, from v1 to vn . The ith vertex ineach case is a vertex with the largest degree, back degree, and forward degree, respectively, among
the vertices that are yet to be ordered. The heuristic intuition here is that in the course of a greedy
algorithm, vertices that are more constrained in the choice of colors get colored early, and thus thealgorithm would use fewer colors compared to, say, an arbitrary order. Among the three, ID uses
the most accurate measure of “constraint”.
An SL ordering is defined right-to-left, from vn to v1 , and the ith vertex is a vertex with thesmallest back degree among vertices that are yet to be ordered. In comparison with LF, ID andDLF, an SL ordering aims at minimizing a mathematically better defined objective. Let Bπ (G)denote the maximum back degree in a vertex ordering π. It is easy to see that a greedy algorithm
that uses the ordering π to color G will use at most Bπ (G) + 1 colors. Different vertex orderings
could result in different maximum back degrees. An SL-ordering gives the minimum maximum
back-degree over all possible orderings, i.e. BSL = B ∗ = minπ Bπ (G), where the minimum is taken∗

Department of Computer Science and Computing Research Institute, Purdue University, West Lafayette, IN,{agebreme, dnguyen, apothen}@purdue.edu†Was involved in part of this work while he was a student at Old Dominion University. Currently at Microsoft
Corporation, Redmond, WA, aritar@gmail.com

1Ordering
Largest FirstIncidence Degree
Dynamic LF
Smallest Last

Propertyfor i = 1 to n:vi has largest degree in V \ {v1 , v2 , . . . vi−1 }for i = 1 to n:vi has largest back degree in V \ {v1 , v2 , . . . , vi−1 }for i = 1 to n:vi has largest forward degree in V \ {v1 , v2 , . . . , vi−1 }for i = n to 1:
vi has smallest back degree in V \ {vn , vn−1 , . . . , vi+1 }Table 1: Properties of degree-based ordering techniques, restricted to distance-1 coloring.

Jacobian
HessianJacobian
Hessian

1d partition
distance-2 coloringstar coloring
NAacyclic coloring

2d partition
star bicoloringNA
acyclic bicoloring
NADirect
DirectSubstitution
Substitution

Table 2: Overview of graph coloring models in computation of derivative matrices. The Jacobian is represented byits bipartite graph, and the Hessian by its adjacency graph. NA stands for not applicable.

over the n! possible vertex orderings. The quantity BSL (G) + 1 is a graph property appropriately
known as the coloring number col(G) of G. We will discuss the interesting connection the parametercol(G) has with several other graph concepts, including degeneracy, core, and arboricity.
In addition to their amenability for description in terms of merely back and forward degrees, theordering techniques listed in Table 1 are also attractive for their time complexities. Each of themcan be implemented to run in linear time in the number of edges in a graph; this is not true forordering techniques such as Saturation Degree. We have included such efficient implementations
in ColPack, our software package for graph coloring and related problems in sparse derivativecomputation.
Besides distance-1 coloring, ColPack contains implementations of efficient algorithms for a variety of graph coloring problems in derivative computation. Table 2 gives an overview of these
problems and the computational scenarios under which they arise. We have adapted the ordering
techniques listed in Table 1 to suit these specialized coloring problems. The adaptation involves
extending the notion of degree, since the algorithms involve visits to the distance-2 neighborhoodof a vertex in a graph or the coloring is performed on a bipartite graph. In ColPack, each ordering
technique adapted for the specialized coloring problem is implemented in such a way that its timecomplexity is upper-bounded by the complexity of the relevant coloring algorithm.
We will present experimental results that compare the ordering techniques—both for the distance1 coloring and the specialized coloring cases—against each other (and against other orderings suchas natural and random) in terms of number of colors used and runtime. The experiments are conducted on large graphs drawn from various application areas as well as on synthetically generated
graphs representing different graph classes. The experiments reveal, among other things, that aDLF ordering is especially effective for star bicoloring of some matrix structures and that an SLordering enables a greedy algorithm to distance-1 color any planar graph using at most 6 colors.

2