4.3: Забарвлення

Template:MathJaxLevin

Картографісти у вигаданій землі Ейлерії намалювали кордони різних герцогств землі. Щоб зробити карту гарною, вони хочуть розфарбувати кожен регіон. Сусідні регіони повинні бути пофарбовані по-різному, але ідеально добре пофарбувати дві віддалені області однаковим кольором. Які найменші кольори можуть використовувати картографісти і все ще виконують це завдання?

Мабуть, найвідомішою проблемою теорії графів є те, як розфарбувати карти.

Враховуючи будь-яку карту країн, штатів, округів тощо, скільки кольорів потрібно для фарбування кожного регіону на карті, щоб сусідні регіони були пофарбовані по-різному?

Фактичні виробники карт зазвичай використовують близько семи кольорів. З одного боку, вони вимагають, щоб водянисті області були певного кольору, а з великою кількістю квітів легше знайти допустиму забарвлення. Ми хочемо знати, чи є менша палітра, яка буде працювати для будь-якої карти.

Як це пов'язано з теорією графів? Ну, якщо ми розмістимо вершину в центрі кожного регіону (скажімо, в столиці кожної держави), а потім з'єднаємо дві вершини, якщо їх стани поділяють межу, ми отримаємо граф. Забарвлення областей на карті відповідає розфарбовуванню вершин графа. Оскільки сусідні області не можуть бути пофарбовані однаково, наш граф не може мати вершини, пофарбовані однаково, коли ці вершини є сусідніми.

Загалом, на будь-якому$G\text{,}$ графіку забарвлення вершин називається (не дивно) забарвленням вершин. Якщо забарвлення вершин має властивість, що сусідні вершини забарвлюються по-різному, то забарвлення називається правильною. Кожен граф має належне забарвлення вершин. Наприклад, ви можете забарвити кожну вершину іншим кольором. Але часто можна вчинити і краще. Найменша кількість кольорів, необхідних для отримання належної вершинної забарвлення, називається хроматичним числом графіка, написаного$\chi(G)$.

Приклад$\PageIndex{1}$: chromatic numbers

Знайдіть хроматичне число графіків нижче.

Рішення

Графік зліва$K_6\text{.}$ The only way to properly color the graph is to give every vertex a different color (since every vertex is adjacent to every other vertex). Thus the chromatic number is 6.

Середній графік можна правильно пофарбувати лише трьома кольорами (червоний, синій та зелений). Наприклад:

Немає можливості розфарбувати його лише двома кольорами, оскільки є три вершини взаємно суміжні (тобто трикутник). Таким чином, хроматичне число дорівнює 3.

Графік праворуч просто$K_{2,3}\text{.}$ As with all bipartite graphs, this graph has chromatic number 2: color the vertices on the top row red and the vertices on the bottom row blue.

It appears that there is no limit to how large chromatic numbers can get. It should not come as a surprise that $K_n$ has chromatic number $n\text{.}$ So how could there possibly be an answer to the original map coloring question? If the chromatic number of graph can be arbitrarily large, then it seems like there would be no upper bound to the number of colors needed for any map. But there is.

The key observation is that while it is true that for any number $n\text{,}$ there is a graph with chromatic number $n\text{,}$ only some graphs arrive as representations of maps. If you convert a map to a graph, the edges between vertices correspond to borders between the countries. So you should be able to connect vertices in such a way where the edges do not cross. In other words, the graphs representing maps are all planar!

So the question is, what is the largest chromatic number of any planar graph? The answer is the best known theorem of graph theory:

Theorem $\PageIndex{1}$: The Four Color Theorem

If $G$ is a planar graph, then the chromatic number of $G$ is less than or equal to 4. Thus any map can be properly colored with 4 or fewer colors.

We will not prove this theorem. Really. Even though the theorem is easy to state and understand, the proof is not. In fact, there is currently no “easy” known proof of the theorem. The current best proof still requires powerful computers to check an unavoidable set of 633 reducible configurations. The idea is that every graph must contain one of these reducible configurations (this fact also needs to be checked by a computer) and that reducible configurations can, in fact, be colored in 4 or fewer colors.

Coloring in General

!

The math department plans to offer 10 classes next semester. Some classes cannot run at the same time (perhaps they are taught by the same professor, or are required for seniors).

Class:	Conflicts with:
A	D I
B	D I J
C	E F I
D	A B F
E	H I
F	I
G	J
H	E I J
I	A B C E F H
J	B G H

How many different time slots are needed to teach these classes (and which should be taught at the same time)? More importantly, how could we use graph coloring to answer this question?

Cartography is certainly not the only application of graph coloring. There are plenty of situations in which you might wish partition the objects in question so that related objects are not in the same set. For example, you might wish to store chemicals safely. To avoid explosions, certain pairs of chemicals should not be stored in the same room. By coloring a graph (with vertices representing chemicals and edges representing potential negative interactions), you can determine the smallest number of rooms needed to store the chemicals.

Here is a further example:

Example $\PageIndex{3}$

Radio stations broadcast their signal at certain frequencies. However, there are a limited number of frequencies to choose from, so nationwide many stations use the same frequency. This works because the stations are far enough apart that their signals will not interfere; no one radio could pick them up at the same time.

Suppose 10 new radio stations are to be set up in a currently unpopulated (by radio stations) region. The radio stations that are close enough to each other to cause interference are recorded in the table below. What is the fewest number of frequencies the stations could use.

Solution

Represent the problem as a graph with vertices as the stations and edges when two stations are close enough to cause interference. We are looking for the chromatic number of the graph. Vertices that are colored identically represent stations that can have the same frequency.

This graph has chromatic number 5. A proper 5-coloring is shown on the right. Notice that the graph contains a copy of the complete graph $K_5$ so no fewer than 5 colors can be used.

У наведеному вище прикладі хроматичне число було 5, але це не контрприклад теоремі чотирьох кольорів, оскільки графік, що представляє радіостанції, не є планарним. Було б непогано мати швидкий спосіб знайти хроматичне число (можливо, неплоского) графіка. Виявляється, ніхто не знає, чи існує ефективний алгоритм обчислення хроматичних чисел.

Хоча ми, можливо, не зможемо легко знайти точне хроматичне число графіка, ми часто можемо дати розумний діапазон для хроматичного числа. Іншими словами, ми можемо дати верхню і нижню межі для хроматичного числа.

Це насправді не дуже складно: для кожного графіка$G\text{,}$ the chromatic number of $G$ is at least 1 and at most the number of vertices of $G\text{.}$

What? You want better bounds on the chromatic number? Well you are in luck.

A clique in a graph is a set of vertices all of which are pairwise adjacent. In other words, a clique of size $n$ is just a copy of the complete graph $K_n\text{.}$ We define the clique number of a graph to be the largest $n$ for which the graph contains a clique of size $n\text{.}$ Any clique of size $n$ cannot be colored with fewer than $n$ colors, so we have a nice lower bound:

Theorem $\PageIndex{2}$

The chromatic number of a graph $G$ is at least the clique number of $G\text{.}$

There are times when the chromatic number of $G$ is equal to the clique number. These graphs have a special name; they are called perfect. If you know that a graph is perfect, then finding the chromatic number is simply a matter of searching for the largest clique.⁴There are special classes of graphs which can be proved to be perfect. One such class is the set of chordal graphs, which have the property that every cycle in the graph contains a chord—an edge between two vertices in of the cycle which are not adjacent in the cycle. However, not all graphs are perfect.

For an upper bound, we can improve on “the number of vertices” by looking to the degrees of vertices. Let $\Delta(G)$ be the largest degree of any vertex in the graph $G\text{.}$ One reasonable guess for an upper bound on the chromatic number is $\chi(G) \le \Delta(G) + 1\text{.}$ Why is this reasonable? Starting with any vertex, it together with all of its neighbors can always be colored in $\Delta(G) + 1$ colors, since at most we are talking about $\Delta(G) + 1$ vertices in this set. Now fan out! At any point, if you consider an already colored vertex, some of its neighbors might be colored, some might not. But no matter what, that vertex and its neighbors could all be colored distinctly, since there are at most $\Delta(G)$ neighbors, plus the one vertex being considered.

In fact, there are examples of graphs for which $\chi(G) = \Delta(G) + 1\text{.}$ For any $n\text{,}$ the complete graph $K_n$ has chromatic number $n\text{,}$ but $\Delta(K_n) = n-1$ (since every vertex is adjacent to every other vertex). Additionally, any odd cycle will have chromatic number 3, but the degree of every vertex in a cycle is 2. It turns out that these are the only two types of examples where we get equality, a result known as Brooks' Theorem.

Theorem $\PageIndex{3}$: Brooks' Theorem

Any graph $G$ satisfies $\chi(G) \le \Delta(G)\text{,}$ unless $G$ is a complete graph or an odd cycle, in which case $\chi(G) = \Delta(G) + 1\text{.}$

The proof of this theorem is just complicated enough that we will not present it here (although you are asked to prove a special case in the exercises). The adventurous reader is encouraged to find a book on graph theory for suggestions on how to prove the theorem.

Coloring Edges

The chromatic number of a graph tells us about coloring vertices, but we could also ask about coloring edges. Just like with vertex coloring, we might insist that edges that are adjacent must be colored differently. Here, we are thinking of two edges as being adjacent if they are incident to the same vertex. The least number of colors required to properly color the edges of a graph $G$ is called the chromatic index of $G\text{,}$ written $\chi'(G)$.

Example $\PageIndex{3}$

Six friends decide to spend the afternoon playing chess. Everyone will play everyone else once. They have plenty of chess sets but nobody wants to play more than one game at a time. Games will last an hour (thanks to their handy chess clocks). How many hours will the tournament last?

Solution

Represent each player with a vertex and put an edge between two players if they will play each other. In this case, we get the graph $K_6\text{:}$

Ми повинні розфарбувати краю; кожен колір представляє різну годину. Оскільки різні ребра, що потрапляють на одну і ту ж вершину, будуть пофарбовані по-різному, жоден гравець не буде грати в дві різні ігри (ребра) одночасно. Таким чином, нам потрібно знати хроматичний індекс$K_6\text{.}$

Notice that for sure $\chi'(K_6) \ge 5\text{,}$ since there is a vertex of degree 5. It turns out 5 colors is enough (go find such a coloring). Therefore the friends will play for 5 hours.

Interestingly, if one of the friends in the above example left, the remaining 5 chess-letes would still need 5 hours: the chromatic index of $K_5$ is also 5.

In general, what can we say about chromatic index? Certainly $\chi'(G) \ge \Delta(G)\text{.}$ But how much higher could it be? Only a little higher.

Theorem $\PageIndex{4}$: Vizing's Theorem

For any graph $G\text{,}$ the chromatic index $\chi'(G)$ is either $\Delta(G)$ or $\Delta(G) + 1$.

At first this theorem makes it seem like chromatic index might not be very interesting. However, deciding which case a graph is in is not always easy. Graphs for which $\chi'(G) = \Delta(G)$ are called class 1, while the others are called class 2. Bipartite graphs always satisfy $\chi'(G) = \Delta(G)\text{,}$ so are class 1 (this was proved by König in 1916, decades before Vizing proved his theorem in 1964). In 1965 Vizing proved that all planar graphs with $\Delta(G) \ge 8$ are of class 1, but this does not hold for all planar graphs with $2 \le \Delta(G) \le 5\text{.}$ Vizing conjectured that all planar graphs with $\Delta(G) = 6$ or $\Delta(G) = 7$ are class 1; the $\Delta(G) = 7$ case was proved in 2001 by Sanders and Zhao; the $\Delta(G) = 6$ case is still open.

There is another interesting way we might consider coloring edges, quite different from what we have discussed so far. What if we colored every edge of a graph either red or blue. Can we do so without, say, creating a monochromatic triangle (i.e., an all red or all blue triangle)? Certainly for some graphs the answer is yes. Try doing so for $K_4\text{.}$ What about $K_5\text{?}$ $K_6\text{?}$ How far can we go?

The answer to the above problem is known and is a fun problem to do as an exercise. We could extend the question in a variety of ways. What if we had three colors? What if we were trying to avoid other graphs. The surprising fact is that very little is known about these questions. For example, we know that you need to go up to $K_{17}$ in order to force a monochromatic triangle using three colors, but nobody knows how big you need to go with more colors. Similarly, we know that using two colors $K_{18}$ is the smallest graph that forces a monochromatic copy of $K_4\text{,}$ but the best we have to force a monochromatic $K_{5}$ is a range, somewhere from $K_{43}$ to $K_{49}\text{.}$ If you are interested in these sorts of questions, this area of graph theory is called Ramsey theory. Check it out.