Graph Coloring

 

Types of Graphs

(other than monograph *wink*)

Y A graph (G) is composed of a set of vertices (V) and a set of edges (E) connecting some or all of the vertices. If u, v Î V and an edge connecting those vertices is in E, then we write G = (V, E}, u, v Î V and {u, v} Î E. Sometimes, we can write V(G) and E(G) to denote the sets of vertices and edges, respectively.

Y A subgraph of G, G', is composed of a subset V' Í V and a subset E' Í E. A generated subgraph of G is composed of a subset of V and all of the edges in E connecting the vertices in the subset; that is, if u, v Î V' and {u, v} Î E, then {u, v} Î E'.

Y A connected graph is a graph in which there exists a path of edges between every vertex and every other vertex. That is, if v1, vn Î V, then there are vertices v2,..., vn-1 Î V such that {v1, v2},..., {vn-1, vn}Î E. Intuitively, a connected graph is a single component.

Y A complete graph, or clique, is a graph for which all vertices have an edge connecting them.

(*) Starting with n vertices, we go to each vertex, vi, and draw an edge to all the other vertices that don't already share an edge with it. Begin at one vertex, v1, and draw an edge to the remaining n - 1 vertices. Go to the second vertex, v2, and draw an edge to the remaining n - 2 vertices--not including the first vertex because there's already an edge connecting v1 and v2. And so forth. So, if the number of vertices is |V| = n, then the number of edges is |E| = Σx = 1,...,n-1x. Note: A clique could be a subgraph of a bigger graph.

(*) A graph with k vertices is a clique iff k is the smallest number such that the graph is k-colorable. If G is a clique then any two vertices of the same color would be connected. Hence, all vertices must be a different color. If G is not a clique, then there exist two vertices that do not share an edge. Those 2 vertices can be the same color while the remaining k - 2 vertices are different colors. So, if G is not a clique, then there is some k' < k such that G is k'-colorable.

(*) Let p be the number of vertices (v1, v2,..., vp) in the largest clique of a connected graph, G. Then G must require at least p different colors to cover the clique. If k is the smallest number such that G is k-colorable, then pk. If k > p, then there is a vertex, vp+1, that requires a color not found in the clique. But then the generated subgraph of vertices (v1, v2,..., vp+1) is (p + 1)-colorable and has p + 1 vertices, making it a larger click. #Contradiction. (Although I usually eschew proofs by contradiction. Brute force is far more conducive to elegant algorithms and smooth computer programs.)

Y A circuit with n vertices is a path (sequence) between two vertices in V such that E Ê {{v1, v2}, {v2, v3},..., {vn-1, vn}, {vn, v1}}

Y A digraph, or directed graph, tells us which way we're going on any given edge (usually in the form of a little arrow-looking thingy right on the edge). So, we'll know whether we can go from v1 to v2 or vice versa or, as in the case of a two-way street, both.

Y An intersection graph is a graph (or hypergraph, Ω(H), or intersection graph of F, Ω(F)) of a family of sets, F = {S1, S2,..., Sn}, where the vertices represent the sets and the edges are formed when distinct sets share elements. That is, V = F = {S1, S2,..., Sn}and E = {{ Si, Sj}| Si Sj} ≠ Ø, ij}. This definition is a modified version of that given by Roberts (1976). Other definitions, such as that from a Hamburg site, define the vertices as the union of the elements of the sets, È i=1,...n Si and the hyperedges as the sets (S1,..., Sn). Mathworld brings these concepts together somewhat by defining a graph G as an intersection graph if there exists a family F of subsets such that G and Ω(F) are isomorphic graphs, i.e. the graphs have the same number of vertices and are connected in the same way.

(*) By Marczewski's (1945) Theorem, all graphs are intersection graphs letting Su = {{u, v} | {u, v} Î E} for all u Î V.

Y An interval graph is essentially the intersection graph of a family of intervals on a line. Each line segment represents a vertex and if two line segments intersect, then they are connected by an edge in the graph.

(*) Not every graph is an interval graph. Consider a circuit with n vertices. Then E = {{1, 2}, {2, 3}, ..., {{n - 1, n}, {n, 1}}} so that, for an interval graph, every edge would overlap the preceding and succeeding edge but the first and last edges would also overlap. The result would be circular rather than linear.

(*) Every interval graph is g -perfect, i.e. for every generated subgraph of an interval graph, the chromatic number is equal to the clique number (X(G') = v (G')). If 2 line segments overlap, then they have two different colors. If p line segments intersect each other (each line segment intersects the other p - 1 line segments, producing a clique in the graph), then they must have p different colors. (If the clique has 2p vertices, then they have 2p different colors. Say it out loud. It's funny. Crude, but funny. Math jokes tend to be graphic.) Consider the connected components of the interval graph. Every component is a connected subgraph and, therefore, the number of vertices in its largest clique is the minimum number of colors required to color the component. The largest clique in the interval graph must be in one of those connected components--otherwise it would be connecting two disconnected components. If the largest clique is k-colorable, then the component containing the largest clique is k-colorable and all the other components containing cliques of less than or equal to k vertices can be colored in the same k or fewer colors.


Concepts in Graph Coloring

Y Colorability: The idea is to color the vertices of a graph G such that no two vertices connected by an edge are the same color. Here we delve into partitioning. A graph G is k-colorable if the set of vertices (V) of G can be partitioned into k classes.

Y Chromatic Number: For the most part, graph coloring problems seek the smallest number of colors to accomplish colorability. The smallest k such that a graph G is k-colorable is know as its chromatic number and denoted X(G) = k.

Y Degree of a vertex, u: δ(u) = the number of vertices connected to u by an edge.

Y D (u) = the maximum δ(u) for u Î V.

Y Clique Number, ω (G): The number of vertices in the largest subgraph of G that is a clique. Note: In graph coloring, every vertex of a clique must be of a different color. If X(G) = v (G), then G is said to be weakly g -perfect. If every generated subgraph, G', of G has X(G') = v (G'), then G is said to be g -perfect.

Theorems

Y A graph G is 2-colorable iff it has no circuits of odd length.

Y

Four Color Problem

Y This is a classic problem dating back to the 19th century. Given a map (or line drawing), color the regions so that no two regions bordering one another are the same color. Can this always be done with four or fewer colors? Note: Kissing corners don't count as boundaries.

Y The graphical design allots a vertex to each region and an edge between bordering regions. This will produce a planar graph in which no two edges can cross except at a vertex. This might/might not be essential in the ultimate proof of the Four-Color Theorem, but it's a kinda neat observation.

Y Actually, some Brits have a cool page on the history and making of the Four-Color Theorem. (Well, in their case, the Four-Colour Theorem. They spell both "four" and "colour" with a "u"! Those wacky Brits!)

Links and Thinks

Y There's a fabulously fun program from a Canadian educational site called the Colorful Mathematics project. Don't forget the pkunzip program when you download it.

Y There's a good online (fairly quick) lesson program from the University of Minnesota.

.:: Home ::.