Graphs And Graph Coloring: Techniques And Algorithms

Apply critical analysis and reflection to ethically research, synthesise and evaluate complex information, problems, concepts, interpretations and theories to demonstrate cognitive and technical skills in a body of knowledge or practice.

Through student demonstration of an advanced and integrated understanding of a complex body of knowledge in one or more discipline areas of  IT.
Through student capacity to extract relevant information from a set of selfselected sources
Through student competence in evaluating the need for research by applying critical analysis and reflection to published scholarly work, derive research ideas, methodological concepts, interpretations and theories.

Graph Theory and Its Applications

A graph is comprised of vertices and edges. The edges connect the vertices to each other hence graphs are deemed as sets of vertices and edges. The edge is termed a multi-set as its elements are found to occur more than once where every element has a multiplicity. For instance, two vertices are end vertices of  a single edge. Graphs with no edges are considered empty and when edges are drawn, the graph is considered simple where it may have no parallel edges or loops. Therefore, a graph is a binary relation whose illustration demonstrates a set of points or nodes connected by edges or arcs. Graphs can be directed or undirected, labeled or unlabeled. The graph models regard the nodes as random variables and the edges as the statistical dependencies between the variables. The illustration in the figure below demonstrate the interaction such that,

These graphs represent visual aspects of electrical circuit diagram, network diagrams, and family trees. They allow one to perceive the abstraction that lies in the conditional independence relationships between the variables from the details of their parametric forms. The models enable one to define message passing algorithms that implement probabilistic inference. In such a situation, the graphical model is able to determine the relationship among many latent variables (Szabó and Zaválnij, 2014).

The intention of the graph modeling techniques, incorporating computer science and high level programming, is to perform the probabilistic modeling. A planar graph is drawn on canvas on the condition that none of the edges are seen to cross. For instance, the map of the east Wales region is drafted on canvas from its three-dimensional state to a two-dimensional planar graph. This literature synthesis seeks to discuss the happy coloring and the algorithms used to develop and color planar graphs on a large scale. The planar graph may be vertex colored with only two colors as long as it is within the polynomial time.

• To develop better algorithms that find the highest number of happy vertices that can be attained with regards to specific families of graphs.
• To determine the small sets of nodes which when removed from the graphs, they manage to maintain the vertices as happy.
• To determine the most suitable algorithm that guarantees proper happy coloring using programming skills.

A section of the global population suffers from color blindness and they are limited to certain colors while the confuse others. The graph coloring techniques originated from the graphical models done by Francis Guthrie. His work was modified by many mathematicians over the years. He proposed that a graph only needed a maximum of four colors to represent all its features. The colors were setup such that the random variables being represented could be uniquely identified. For instance, one of the famous works discussed is the illustration of the regions in Wales. The key consideration in the illustration ensures that the neighboring regions do not get the same color as a certain region. The graphical models use the four-color theorem to demystify this modeling technique. In this example, the regions are marked out as vertices and edges are added to the different vertices such that no neighboring regions get the same color. The regions marked out tend to be quite small scale.

Types of Graphs

The regions are mapped out and colored using no more than four colors. Another key example that requires proper coloring is the school timetable or duty roster in an industry or security company. For the school timetable, each room has a different color. Alternatively, each course taken in the different rooms is assigned a color such that one can expressly tell which class they have without reading through the description section. In a college setting where the facilities are inadequate, there is need to develop an algorithm to have student in different courses sit in the same room doing different tests. Wedding or event planners handle the seating arrangements for the guests to ensure that people are well matched with their seatmates. Some of the real-world applications present a complex scenario and a well-developed algorithm must be generated to determine the sitting arrangement, or timetabling plan. The graph coloring can be used in designing and playing games such as mini Sudoku. These real-life application require a level of cognitive action to determine the solution. The graph coloring algorithm adopted for the different cases helps one solve the problem a bit faster and ensure a higher level of accuracy.

The greed or sequential coloring of a graph seeks to have the vertex colored such that no two adjacent vertices have the same color(Cherkashin and Kozik, 2014). Several algorithms have been developed to ensure that the least number of colors is used in the graph coloring process. The proper coloring of a graph ensures that k colors are used. The least number of color needed in a particular graph coloring is termed as the chromatic number which is usually k (Detecting Overlapping Nodes in MLM Chain Network, 2017). The happy coloring is based on the condition of the vertex-colored graph such that, G=( V,E ). Happy edges have endpoints with similar colors while happy vertices observe similar color in all their neighboring vertices. As a result, a vertex is happy when all the incident edges are happy. The graph coloring is, equally, used to model resource allocations to entities in the network. The algorithms or pattern search techniques seek to ensure that the maximum number of happy vertices is observed (Du et al., 2013). The least number of colors is required as per the 4 color theorem hence; some experiments have tested the application of a single color to the neighboring nodes. The solution is quite trivial as the viewer may not differentiate one region from another or a given class from another. As a result, the greedy algorithm is designed such that the number of colors employed is desired as k+1 color. The least number of colors that can be used in such a case are 2 and the maximum or the highest chromatic number is 3. This, therefore, affirms the 4 color theorem in the proper vertex coloring (Edu, 2018). 

Graph Models and Probabilistic Modeling

The greedy coloring algorithm picks on the next vertex to be colored in a sequential manner. It ensures that the color chosen for a certain vertex does not change as the algorithm moves forward to the next vertex (Hertz, Montagné and Gagnon, 2016). The first fit arranges the vertices and assigns the lowest legal color based on the RGB values of the chosen colors. It runs on the algorithm run time highlighted in the research methodology. The algorithm is a good fit for small scale graphical model coloring. The degree based ordering uses a criterion to determine the vertex colored. The vertex coloring is not sequential rather it is picked on an arbitrary order. The largest degree ordering chooses the vertex with the maximum number of neighbors to assign a color (Meghanathan, 2016). The algorithm carries on until it colors the final vertex based on the same approach. The greedy approximation ratio is given as,

The literature review section analyses the different application areas that require the use of the 4-color theorem. There are complex graphical models such as the seating arrangement and the exam timetable scheduler that require a higher level of coloring scheme especially where the maximum number of colors is set to four. The research paper seeks to determine if there is a suitable algorithm that can form happy vertices for the real-world applications using the least number of colors (Szabó and Zaválnij, 2014).

Greedy coloring & happy coloring algorithm

• By hand
• By computer simulation

The graph coloring proposed algorithms seek to ensure that the coloring of the nodes on the graph is done with the least number of colors. This is presented as an optimization problem that may find the vertex coloring with the minimum number of colors. The tests are done using hand experiments or computer simulation software based on the proposed algorithm (Princeton, 2018). The chromatic number of G will represent the minimum number of colors required to color the vertices of G in the NP-complete problem. There are heuristic graph coloring algorithms such as the first fit, degree based ordering, largest degree ordering, incident degree ordering, and the saturation degree ordering. These algorithms are based on the running time,

The proposed algorithm seeks to color up to 3 vertex graphs with certain number of colors such as,

Based on the greedy coloring heuristic algorithm, the largest and saturation degree ordering stood out as viable algorithms. However, they need modification to improve on the run time as well as color on the vertices. The algorithm combines the activities of the SDO and the LDO to incorporate the benefits of both ordering schemes. An algorithm details the steps followed when performing a particular simulation or task (Wu and Ma, 2013). The algorithm can be implemented by hand when the graphical model is quite simple or less structured but it requires a higher-level of programming either in C++, python,or PhP to implement in a computer simulation environment. The algorithm or pseudo-code follows as such,

1. Start
2. Enter the set of nodes or graphical edges as an array or vector
3. Determine the vertex with maximum number of neighbors.
4. Test if there are vertices with the same degree or the same number of neighbors surrounding them.
5. Run the saturation degree ordering to determine the number of the adjacent vertices that are differently colored.  
6. Output the colored nodes alongside the number of the colors used in developing the graphical model coloring.
7. End

The Four-Color Theorem and Graph Coloring

Step c and d require the use of a loop to determine whether to focus on the number of colors that surround the vertex or the number of vertices surrounding the colored vertex (Zewi, 2011). The while loop is used in such a situation such that,

while(ColoredNodes_Number<n)

{

max=-1;

for k=1:n

{

if (!colored_vertex(n(k)))

{

“use the saturated degree ordering to color a region”

d=SDO(n(k))

if(d>max)

{

max=d

index=i

}

if (d=max)

{

if (Degree(nk)>Degree(n(index))

{

index=k;

Degree(n(index))

}

}

}

“The results are obtained as follows”

color(n(index))

ColoredNodes_Number=ColoredNodes_Number+1;

}

}

The algorithm is tested on computer simulation software to determine a bit more complex tests such as the seating arrangement in a wedding or large event. The computer simulation operates on the run time as computed in the methodology. Data is collected and further tests are carried out to ensure that the algorithm works well. The data is used to train the simulator using different sets of vectors detailing the node arrangement. Random graphs are used to test the simulator to determine the effectiveness of the algorithm in managing the happy coloring in the graphical models. The new algorithm performs better than the other algorithms that have been discussed in the literature review. The NP-complete problem seeks to determine whether the planar graph can be colored with 3 colors. Under the 4-color theorem scheme the planar graph is vertex colored with only four colors.

Conclusion

In a nutshell, graphs are comprised of a set and multi set of edges and vertices. The graphical models are used to represent real-life applications such as the mini Sudoku game, the seating arrangement, and the exam timetabling plan. The happy coloring is such that the edge is considered happy when it is not adjacent to a similar colored vertex.  The greed coloring colors the vertices in a sequential manner. The greedy coloring has a limitation in that the sequential coloring may result in some vertices having same colors as their adjacent vertices. Several heuristic algorithms are modeled to overcome the caveats presented by the greedy coloring scheme. The literature synthesis proposes a new algorithm that borrows from the saturation degree ordering and largest degree ordering schemes under the heuristic algorithms. The algorithm runs on the highlighted run time and performs adequately when tested using random graphs.

References

Cherkashin, D. and Kozik, J. (2014). A note on random greedy coloring of uniform hypergraphs. Random Structures & Algorithms, 47(3), pp.407-413.

Detecting Overlapping Nodes in MLM Chain Network. (2017). International Journal of Science and Research (IJSR), 6(7), pp.572-575.

Du, R., Zhao, C., Zhao, F. and Li, S. (2013). Strategies of network coding against nodes conspiracy attack. Security and Communication Networks, 8(14), pp.2396-2403.

Edu, C. (2018). [online] People.cs.uchicago.edu. Available at: https://people.cs.uchicago.edu/~laci/14algorithms/greedycoloring.pdf  [Accessed 1 Sep. 2018].

Hertz, A., Montagné, R. and Gagnon, F. (2016). Constructive algorithms for the partial directed weighted improper coloring problem. Journal of Graph Algorithms and Applications, 20(2), pp.159-188.

Kozik, J. (2015). Multipass greedy coloring of simple uniform hypergraphs. Random Structures & Algorithms, 48(1), pp.125-146.

Math, M. (2018). [online] Maths.manchester.ac.uk. Available at: https://www.maths.manchester.ac.uk/~mrm/Teaching/DiscreteMaths/Slides/GraphColouringSlides.pdf  [Accessed 1 Sep. 2018].

Meghanathan, N. (2016). A Greedy Algorithm for Neighborhood Overlap-Based Community Detection. Algorithms, 9(1), p.8.

Princeton, E. (2018). [online] Web.math.princeton.edu. Available at: https://web.math.princeton.edu/math_alive/5/Notes2.pdf  [Accessed 1 Sep. 2018].

Szabó, S. and Zaválnij, B. (2014). Coloring the nodes of a directed graph. Acta Universitatis Sapientiae, Informatica, 6(1), pp.117-131.

Wu, Y. and Ma, H. (2013). Logistics Network Nodes Importance Analysis Based on the Complex Network Theory. Applied Mechanics and Materials, 336-338, pp.2410-2414.

Zewi, N. (2011). Vector representation of graph domination. Journal of Graph Theory, 70(2), pp.152-170.