Sigma Graph Coloring (Tuklas Vol. 17, No. 4 - October 10, 2015)

SIGMA GRAPH COLORING

Figure 1: Graph \(G\) with 3 vertices and 3 edges

Consider the figure above. This object is called a graph, and it can be used to represent a wide variety of things. For instance, it can be used to represent a road network or a map of social relationships. A graph consists of a set of points called vertices, where some pairs of vertices are joined by a line called an edge. We say that the two vertices \(v_1\) and \(v_2\) are adjacent if there is an edge \(e\) that connects \(v_1\) and \(v_2\).

For any vertex \(v\) in \(G\), the neighbor of \(v\) is the vertex adjacent to \(v\). Looking back at the previous illustration, the vertex \(v_1\) in \(G\) has neighbors \(v_2\) and \(v_3\).

Mathematicians like to play around with graphs, because the properties that can be derived are very interesting. For instance, a vertex coloring of a graph \(G\) refers to an assignment of colors to the vertices in \(G\). We use positive integers \(1,2, \ldots , n\) as colors to be assigned to the vertices in a graph. Why does it have to be positive integers? It is because we are interested in the number of colors to be used. A color sum of a vertex \(v\) is the sum of the colors of the neighbors of \(v\). We write the color sum of \(v\) as \(\sigma\) (sigma).

Moreover, a vertex coloring is a sigma coloring if for any two neighboring vertices, their color sums are not equal. In fact, a graph \(G\) has sigma \(k\)-coloring if we can assign at most \(k\) colors to the vertices in \(G\).

In the figure below, consider a graph with a sigma \(3\)-coloring. We choose the colors \(2\), \(5\), and \(9\) to label the vertices in \(G\).

Figure 2: Sigma 3-coloring of \(G\)

Indeed, as shown above, any two neighboring vertices in \(G\) have distinct color sums. Therefore, \(G\) has sigma \(3\)-coloring.

Notice that the following figure shows sigma colorings of the graph \(H\) with \(6\) vertices and \(6\) edges.

Figure 3: Examples of sigma colorings

We note that any graph with \(n\) vertices has a sigma \(k\)-coloring where, \(1 \leq k \leq n\). However, what if we want to determine the smallest number of colors needed in a sigma coloring of a graph? In other words, we want to find the smallest value of \(k\) in which a sigma \(k\)-coloring exists. The minimum value of \(k\) is called the sigma chromatic number of a graph. Now, we recall the graph \(H\) above. Suppose we assign all the vertices in \(H\) with only one color, say, \(7\).

Figure 4: Not a sigma coloring of \(H\)

The illustration above shows that \(H\) has no sigma \(1\)-coloring because any two neighboring vertices have equal color sum. Since \(H\) is sigma \(2\)-colorable (as shown in (d) above), the sigma chromatic number of \(H\) is \(2\).

Mathematicians have been fascinated by sigma graph coloring not just because of the math involved, but also because of the real life applications. Some of these involve club scheduling problems and hospital planning. Can you think of an application of sigma graph coloring in daily life?

ABOUT THE AUTHOR:
Maria Czarina T. Lagura is a graduate assistant at the Ateneo de Manila University. She is currently taking her Master's degree at the same university.

REFERENCES:

- Chartrand, G. and P. Zhang. Chromatic Graph Theory, Chapman & Hall/CRC Press, Boca Raton, FL (2009).
- Chartrand, G., F. Okamoto, P. Zhang. "The Sigma Chromatic Number of a Graph." Graph and Combinatorics, 26:755-773 (2010).

OLYMPIAD CORNER

from the 51st International Mathematical Olympiad, 2010 (Shortlist)

Problem:  Given six positive numbers \(a\), \(b\), \(c\), \(d\), \(e\), \(f\) such that \(a < b < c < d < e < f\). Let \(a + c + e = S\) and \(b + d + f = T\). Prove that \[ 2ST > \sqrt{3\left( S+T\right) \left( S\left(bd+bf+df\right) +T\left(ac+ae+ce\right) \right) } \]

Solution: 

Let \(\alpha =ac+ce+ae\) and \(\beta =bd+bf+df\). Moreover, let \(s=c+e\), hence \(a=S-s\).

Note that\[ \left( c-b\right) \left( c-d\right) +\left( e-f\right) \left( e-d\right) +\left( e-f\right) \left( c-b\right) < 0, \]since each summand is negative. We can rewrite this as\[ \begin{align} \left( bd+bf+df\right) -\left( ac+ce+ae\right) &< \left( c+e\right) \left( b+d+f-a-c-e\right) \\ \beta -\alpha &< s\left( T-S\right) \end{align} \]and we have\[ S\beta +T\alpha =S\left( \beta -\alpha \right) +\left( S+T\right) \alpha < Ss\left( T-S\right) +\left( S+T\right) \left( ce+as\right) \]Since \(\left( c-e\right) ^{2}\geq 0\), then \(\frac{(c+e)^{2}}{4}\geq ce\).

Hence,\[ S\beta +T\alpha < Ss\left( T-S\right) +\left( S+T\right) \left( \frac{s^{2}}{4}+\left( S-s\right) s\right) =s\left( 2ST-\frac{3}{4}\left( S+T\right) s\right) \]Using the AM-GM Inequality, we have\[ \begin{align} \sqrt{\frac{3}{4}\left( S+T\right) \left( S\beta +T\alpha \right) } & < \sqrt{\frac{3}{4}\left( S+T\right) s\left( 2ST-\frac{3}{4}\left( S+T\right) s\right) } \\ &\leq \frac{\frac{3}{4}\left( S+T\right) s+2ST-\frac{3}{4}\left( S+T\right) s}{2}=ST \end{align} \]Therefore\[ 2ST > \sqrt{3\left( S+T\right) \left( S\left( bd+bf+df\right) +T\left( ac+ae+ce\right)\right)}. \]

PROBLEMS

13. Determine the values of \(x\) such that \(2^{x}+3^{x}-4^{x}+6^{x}-9^{x}\leq1\).
14. Let \(n\), \(a\), and \(b\) be positive integers. Prove that\[ \gcd\left(n^{a}-1,n^{b}-1\right)=n^{\gcd\left(a,b\right)}-1. \]
15. Let \(a\) and \(b\), with \(a\geq b\) be roots of \(x^{2}-3x-50=0\). Determine the value of \(a^{3}-2014b^{2}+2015\).
16. Four spheres have radii \(2\), \(2\), \(3\), and \(3\) respectively. Each sphere is tangent to three others. There is another sphere which is tangent to all these four spheres. Determine the radius of this sphere.
17. Let \(P_{1}P_{2}\dots P_{12}\) be a regular dodecagon. Prove that \(P_{1}P_{5}\), \(P_{4}P_{8}\), and \(P_{3}P_{6}\) are concurrent (they intersect at the same point).
18. For each permutation \(a_{1},a_{2},\dots,a_{2014}\) of the integers \(1, 2, \dots, 2014\), form the sum\[ \sum_{i=1}^{1007}\left|a_{2i-1}-a_{2i}\right|. \]Find the average value of all these sums.

We welcome readers to submit solutions to the problems posed below for publication consideration. Solutions may ONLY be submitted online via vantonio1992@gmail.com. Solutions must be preceded by the solver's name, school affiliation and year level. The deadline for submission is 12:30 PM October 24, 2015.

SOLUTIONS

(for October 3, 2015)

10. Find all values of \(x\), \(y\), and \(z\) such that \(x^4+y^4+z^4-4xyz=-1\).
    (Solved by Jarrett Ian G. Lim [Philippine Academy of Sakya], Joyce Heidi Ong [Chiang Kai Shek College], Ryan Jericho Sy [Chang Kai Shek College], Farrell Eldrian Wu [MGC New Life Christian Academy]; partial credit for Madeline L. Tee [Jubilee Christian Academy])
    
    
    SOLUTION: 
    We have\[ \begin{align*} -1 & = x^{4}+y^{4}+z^{4}-4xyz\\ 0 & = x^{4}+y^{4}+z^{4}-4xyz+1\\ & = \left(x^{4}-2x^{2}y^{2}+y^{4}\right)+\left(z^{4}-2z^{2}+1\right)-4xyz+2x^{2}y^{2}+2z^{2}\\ & = \left(x^{4}-2x^{2}y^{2}+y^{4}\right)+\left(z^{4}-2z^{2}+1\right)+2\left(x^{2}y^{2}-2xyz+z^{2}\right)\\ 0 & = \left(x^{2}-y^{2}\right)^{2}+\left(z^{2}-1\right)^{2}+2\left(xy-z\right)^{2}. \end{align*} \]We have a sum of squares that is equal to 0. This means that each of the terms must be equal to \(0\). From the second term, we have\[ z=\pm1, \]while from the first and the third we get \(x=\pm y\) and \(xy=z\). This means that if \(z=1\), we have the solutions \(\left(\pm1,\pm1,1\right)\), while for \(z=-1\), we have \(\left(\pm1,\mp1,-1\right)\).
11. Find the number of ways to color \(2015\) points on a circle with \(3\) colors such that any two neighboring points have distinct colors.
    (Partial credit for Jarrett Ian G. Lim [Philippine Academy of Sakya], Joyce Heidi Ong [Chiang Kai Shek College], Farrell Eldrian Wu [MGC New Life Christian Academy])
    
    
    SOLUTION: 
    Let us solve the problem for a general number of points \(n\). Define \(a_{n}\) to be the number of possible colorings for \(n\) points on the circle.
    
    Note that if \(n=1\), then \(a_1=3\).
    
    If \(n=2\), then the first point will have three color options, while the other will have one less option. We have \(3\cdot2=6\) possible colorings, and consequently, \(a_{2}=6\).
    
    Now, if \(n=3\), then the first point will have three options, its neighboring point (to the right) will have 2 options, while the remaining point will only have 1. This means that \(a_{3}=3\cdot2\cdot1=6\).
    
    On the other hand, if we have \(n+1\) points. Consider the neighbors of the last added point. We have one color used for the last point. We have two cases.
    
    Consider the case when the two neighbors of this last added point has the same color. If its two neighbors share the same color, then the last added point will have two color options.
    
    Moreover, since the two neighbors have the same color, then we can just consider it as a single point, which means that, along with the rest of the points, the \(n\) points can be colored \(a_{n-1}\) ways. This means, in this first case, we have \(2a_{n-1}\) colorings.
    
    On the other hand, if the two neighbors have different colors, then, there will only be one option for the last added point. Moreover, the rest of the \(n\) points can be colored \(a_{n}\) ways.
    
    This means that we have the recurrence relation (RR)\[ a_{n+1}=a_{n}+2a_{n-1}, \]where \(a_1=2\) and \(a_{2}=a_{3}=6\). The closed form of this RR is given by\[ a_{n}=2^{n}+2\left(-1\right)^{n}. \]If we check, we have\[ \begin{align*} a_{n}+2a_{n-1} & = \left[2^{n}+2\left(-1\right)^{n}\right]+2\left[2^{n-1}+2\left(-1\right)^{n-1}\right]\\ & = 2^{n}+2\left(-1\right)^{n}+2^{n}-4\left(-1\right)^{n}\\ & = 2^{n+1}+2\left(-1\right)^{n+1}\\ & = a_{n+1}. \end{align*} \]Finally, we just need to obtain \(a_{2015}=2^{2015}-2\) colorings.
12. Determine the minimum value of \(\dfrac{a+b+c}{b-a}\) given that for all \(x\), \(ax^2+bx+c\geq 0\) and \(a < b\).
    (Partial credit for Joyce Heidi Ong [Chang Kai Shek College], Ryan Jericho Sy [Chang Kai Shek College], Farrell Eldrian Wu [MGC New Life Christian Academy])
    
    
    SOLUTION: 
    First, note that if \(a=0\), then \(ax^{2}+bx+c=bx+c\). Since \(0=a<b\), then \(b\) is positive, then\[ \begin{align*} bx+c & \geq 0\\ x & \geq -\frac{c}{b}. \end{align*} \]This means that the condition \(ax^{2}+bx+c\geq0\) is only true when \(x\geq-\dfrac{c}{b}\).
    
    This means that \(a\neq0\).
    
    We now have\[ \begin{align*} 0 & \leq ax^{2}+bx+c\\ & = a\left(x^{2}+\frac{b}{a}x+\frac{b^{2}}{4a^{2}}\right)+\frac{4ac-b^{2}}{4a}\\ & = a\left(x+\frac{b}{2a}\right)^{2}+\frac{4ac-b^{2}}{4a}. \end{align*} \]If \(a<0\), then we can solve for \(x\) such that the inequality is true, and certainly, the solution set of this inequality will not be \(\mathbb{R}\), in fact, the values will have to be in the interval\[ \left[\frac{-b-\sqrt{b^{2}-4ac}}{2a},\frac{-b+\sqrt{b^{2}-4ac}}{2a}\right]. \]This means that \(a>0\).
    
    Now, if we want this expression to to always be greater than \(0\), then the right side of the expression must be nonnegative as well. We must have \(4ac-b^{2}\geq0\). This means that \(c\geq\dfrac{b^{2}}{4a}\).
    
    Since we are trying to minimize \(\dfrac{a+b+c}{b-a}\), we can minimize \(c\) first. So we just get\(c=\dfrac{b^{2}}{4a}\). Now,\[ \begin{align*} \frac{a+b+c}{b-a} & = \frac{a+b+\dfrac{b^{2}}{4a}}{b-a}\\ & = \frac{4a^{2}+4ab+b^{2}}{4a\left(b-a\right)}\\ & = \frac{\left(9a^{2}+6ab-6a^{2}\right)+\left(b^{2}-2ab+a^{2}\right)}{4a\left(b-a\right)}\\ & = \frac{9a^{2}+6a\left(b-a\right)+\left(b-a\right)^{2}}{4a\left(b-a\right)}\\ & = \frac{9a}{4\left(b-a\right)}+\frac{3}{2}+\frac{\left(b-a\right)}{4a}. \end{align*} \]Note that \(b-a\) and \(a\) are both positive. By AM-GM, we have\[ \begin{align*} \frac{9a}{4\left(b-a\right)}+\frac{\left(b-a\right)}{4a} & \geq 2\sqrt{\frac{9a}{4\left(b-a\right)}\frac{\left(b-a\right)}{4a}}\\ & = \frac{3}{2}. \end{align*} \]This means that the minimum value of \(\dfrac{a+b+c}{b-a}\) is \(\dfrac{3}{2}+\dfrac{3}{2}=3\). This can be achieved when \(a=1\) and \(b=4\), and \(c=4\). Note that in this case, we have \(x^2+4x+4=\left(x+2\right)^2\geq0\), so the condition is still satisfied.