How to Find a Chromatic Number

Save

In mathematical theory a graph is defined by a set of vertices that are connected together by lines that define the edges. Vertices are the points at which lines meet. Sometimes labeling graphical vertices with colors makes specific mathematical problems easier to solve or understand. The chromatic number is defined as the smallest number of colors required to color vertices, such that no two adjacent vertices share the same color. A real-life example of this concept is the idea of people interacting. Imagine a party for international exchange students, with people from different guest countries and the host country. You want to maximize the multicultural experience, so you say that no two people from the same country can talk to each other. What is the lowest number of nationalities that need to be present in a party with a given number of guests in a given configuration? That's the chromatic number. In general, complex algorithms are required to determine the chromatic number of a complex graph/network, but there are some simple cases in which it can be determined visually.

Things You'll Need

  • Pen
  • Paper
  • Colored pencils

Complete Graph: Triangle

  • Draw a triangle to represent a "complete graph" -- a graph in which each pair of vertices is connected by a line and each line has different vertices at each end. Imagine three party guests sitting together at a triangular table.

  • Notice that the triangle contains three vertices. The guests at the table are our example of these vertices. Complete graphs have a chromatic number that is equal to the number of vertices; therefore the chromatic number of the triangle is equal to 3, but let's look at this more closely to confirm this rule.

  • Use pencils to color each the vertices; each color can represent a different country. We have to color each vertex with a different color in order to ensure that the nearest neighbors do not have the same color. Since this requires three colors, this confirms that the chromatic number is indeed 3. In our example, you would need people from 3 different countries in order to have three guests interacting together with no two of them being of the same nationality.

Cycle Graph: Square

  • Draw a set of vertices defining a square, to represent a cycle graph. A cycle graph is one in which a single line, such as that for a circle, passes through all the vertices. In our example, imagine guests at a square table, and each one can only talk to the person next to them. Again, you want everyone talking to someone from a different country than theirs.

  • Use the appropriate rule to determine the chromatic number of the graph. Cycle graphs have a chromatic number of 3 when the number of vertices is odd and a chromatic number of 2 when the number of vertices is even. Therefore, the chromatic number of a cycle with four defined vertices is equal to 2, but again, let's visualize this situation to illustrate this rule.

  • Use pencils to color each of the vertices; the colors represent countries. Unlike the triangle, not all of the four vertices are adjacent to one another, so only two colors are required. In our example, with only two nationalities present, all four people can avoid talking with someone from their own country.

Complete Graph: Square

  • Now, let's consider the next simplest example of a complete graph, for 4 points. The points are arranged in a square, but each is connected to all of the other points. This looks like a square with an "X" in the middle. In our example, we again have four people seated at a square table, but each person can not only talk to the person next to them, but they can also talk to the person across from them; everyone is connected.

  • Use pencils to color each of the vertices. Again, each color represents a different nationality.

  • Looking at the 6 connections, it will be clear that 4 different vertex colors are needed. In our example, the only way to make sure everyone is always talking with someone from a different country is to have 4 different countries represented. In other words, whereas the chromatic number of a 4-point cycle graph was 2, for a 4-point complete graph, the chromatic number is 4.

References

  • Photo Credit Wavebreakmedia Ltd/Wavebreak Media/Getty Images
Promoted By Zergnet

Comments

Resources

You May Also Like

Related Searches

Check It Out

How to Build and Grow a Salad Garden On Your Balcony

M
Is DIY in your DNA? Become part of our maker community.
Submit Your Work!