Transcript dlaughon_CS594_Presentation

Graph Coloring
David Laughon
CS594 Graph Theory
Definitions
• Coloring – Assignment of labels to vertices
f :V(G) ® S
• k-coloring – a coloring where
S =k
• Proper k-coloring – k-coloring where vertices have different labels if
they are adjacent
• Chromatic number – least k for which G is k-colorable - χ(G)
Definitions
• A Graph is k-chromatic if χ(G) = k
• Optimal coloring – proper k-coloring of a k-chromatic graph
– Vertex-coloring problems
• Is a graph k-colorable for given k?
• What is χ(G) / what is the optimal coloring?
History
• Four-color conjecture – Francis Guthrie, 1852 (F.G.)
– Can any map be colored using at most 4 colors so that adjacent
regions are not the same color?
• Many incomplete proofs (Kempe)
– “Counterexamples”
• 5-color theorem proved in 1890 (Heawood)
• 4-color theorem finally proved in 1977 (Appel, Haken)
– First major computer-based proof
• Graph coloring applies to non-planar graphs as well
4-color “Counterexample”
• Martin Gardner, April 1975
edition of Scientific American
• As an April fool’s joke, claimed
graph required 5 colors
Examples
Proper 6-coloring
Optimal 4-coloring
Examples – Kn
• For complete graphs, χ(G) = n
• Each vertex has n-1 edges that
connect to every other vertex
– Forces each vertex to have
a unique color
Examples
• A graph is 2-colorable iff it is
bipartite
Examples
• ω(G) – size of largest clique in G
• χ(G) ≥ ω(G)
– Clique of size n requires n colors
– Can be a tight bound, but not always
Examples
χ(G) = 7, ω(G) = 5
Examples
• Mycielski’s Construction
– Can be used to make
graphs with arbitrarily
large chromatic numbers,
that do not contain K3 as a
subgraph
Greedy Coloring
• χ(G) ≤ Δ(G) + 1
• Greedy Algorithm:
– Put the vertices of a graph in a sequence
– For each vertex in the sequence, assign it the lowest indexed
color not already assigned to adjacent vertices
• Not guaranteed to be optimal for every possible sequence
• Guaranteed optimal for at least one sequence
Greedy Coloring Example
Vertex
0
1
2
3
4
5
Color
Yellow
Yellow
Yellow
Green
Green
Green
Greedy Coloring Example
Vertex
0
3
1
4
2
5
Color
Yellow
Yellow
Green
Green
Purple
Purple
Kempe Chains
• A path in a graph that
alternates between 2 colors
• First used by Kempe in his
incorrect proof of the 4-color
theorem
• Used in 5-color theorem and 4color theorem proofs
5-color theorem
• All planar graphs can be colored with at most 5 colors
•
•
•
•
Basis step: True for n(G) ≤ 5
Induction step: n(g) > 5
There exists a vertex v in G of degree at most 5 (Theorem 6.1.23)
G – v must be 5-colorable by induction hypothesis
5-color Theorem
• If G is 5-colorable, done
• If G is not 5 colorable, we have:
• Is there a Kempe chain
including v1 and v3?
5-color Theorem
There is no Kempe chain
There is a Kempe chain
5-color Theorem
There cannot be a Kempe chain
including v2 and v4
v4 cannot directly influence v2
Edge Coloring
• Similar to vertex coloring, except edges are colored
– Adjacent edges have different colors
Edge Coloring
• Every edge-coloring problem can be transformed into a vertexcoloring problem
• Coloring the edges of graph G is the same as coloring the vertices in
L(G)
• Not every vertex-coloring problem can be transformed tin an edgecoloring problem
– Every graph has a line graph, but not every graph is a line graph
of some other graph
Edge Coloring
K4 edge-coloring
L(K4) vertex-coloring
Multi-coloring
• Each vertex in G has a positive integer label x(v): the number of
colors that must be assigned to that vertex
• The color sets of adjacent vertices must be disjoint
χ(G) = 5
{Blue}
{Yellow, Green,
Purple, Red}
{Yellow, Green}
{Blue}
Multi-coloring
• Every multi-coloring problem can be transformed to a vertexcoloring problem
– For each vertex with x(v) = n, replace it with a clique of size n.
– Add an edge from each vertex in the new clique to every vertex
that the original vertex was adjacent to.
– Single vertex-coloring now solves the problem
Multi-coloring
χ(G) = 5
Applications
•
•
•
•
•
•
Scheduling
Register allocation
VLSI channel routing
Biological networks (Khor)
Testing printed circuit boards (Garey, Johnson, & Hing)
Sudoku
Applications: Sudoku
• Each cell is a vertex
• Each integer label is a “color”
• A vertex is adjacent to another
vertex if one of the following
hold:
– Same row
– Same column
– Same 3x3 grid
• Vertex-coloring solves Sudoku
State of the Art
•
•
•
•
•
•
Decide if a graph is k-colorable is NP-complete
Determining χ(G) is NP-hard
k-colorable – O(2.445^n) (Lawler)
3-colorable – O(1.3289^n) (Beigel, Eppstein)
4-colorable – O(1.7272^n) (Fomin, Gaspers, & Saurabh)
Alternative methods of solving graph coloring
– Swarm intelligence (Dorrigiv, Markib)
Open Problems
• Hadwiger Conjecture
– Every k-chromatic graph has a subgraph that becomes Kk
through edge contractions
– Open for k ≥ 7
Open Problems
• Erdős–Faber–Lovász
conjecture
– Consider k complete
graphs with exactly k
vertices. If every pair of
complete graphs shares at
most one vertex, then the
union of the graphs can be
colored with k colors
References
•
•
•
•
•
•
•
F. G. (June 10, 1854), "Tinting Maps", The Athenaeum: 726.
Heawood, P. J. (1890), "Map-Colour Theorems", Quarterly Journal of Mathematics,
Oxford 24: 332–338
Appel, Kenneth; Haken, Wolfgang (1977), "Every Planar Map is Four Colorable Part I.
Discharging", Illinois Journal of Mathematics 21: 429–490
Appel, Kenneth; Haken, Wolfgang; Koch, John (1977), "Every Planar Map is Four
Colorable Part II. Reducibility", Illinois Journal of Mathematics 21: 491–567
Appel, Kenneth; Haken, Wolfgang (October 1977), "Solution of the Four Color Map
Problem", Scientific American 237 (4): 108–121
Khor, S., "Application of graph colouring to biological networks," Systems Biology,
IET , vol.4, no.3, pp.185,192, May 2010
Garey, M.R.; Johnson, D.; Hing So, "An application of graph coloring to printed
circuit testing," Circuits and Systems, IEEE Transactions on , vol.23, no.10,
pp.591,599, Oct 1976
References
•
•
•
•
Lawler, E.L. (1976), "A note on the complexity of the chromatic number problem",
Information Processing Letters 5 (3): 66–67
Beigel, R.; Eppstein, D. (2005), "3-coloring in time O(1.3289n)", Journal of
Algorithms 54 (2)): 168–204
Fomin, F.V.; Gaspers, S.; Saurabh, S. (2007), "Improved Exact Algorithms for
Counting 3- and 4-Colorings", Proc. 13th Annual International Conference, COCOON
2007, Lecture Notes in Computer Science 4598, Springer, pp. 65–74
Dorrigiv, M.; Markib, H.Y., "Algorithms for the graph coloring problem based on
swarm intelligence," Artificial Intelligence and Signal Processing (AISP), 2012 16th
CSI International Symposium on , vol., no., pp.473,478, 2-3 May 2012
Homework
• Prove that every graph has a vertex ordering such that the greedy
coloring algorithm produces an optimal coloring
• Given a k-chromatic graph and an optimal coloring of it, prove that
for each color i there is a vertex with color i that is adjacent to
vertices of all the other k-1 colors