A Study on the Significance of Line and Complete Graph with a Reference of N-Coloured Graphs

INTRODUCTION

Speed of operation, measured through computational complexity, is obviously one of the most important features which are taken into consideration when selecting a graph coloring approach. For suboptimal methods, the algorithm‘s performance guarantee is another characteristic feature, describing how accurate, or more precisely how inaccurate the obtained results may be. The analysis of the smallest hard to color graphs is yet another criterium, which in a certain sense complements the performance guarantee. The development of heuristic graph coloring methods is necessary due to the computational complexity of optimal algorithms. Graph coloring is an NP-hard problem in the case of most non-trivial coloring models; in particular there are no known optimal polynomial-time solution. However, the large number of existing suboptimal algorithms necessitates the usage of tools and methods which enable the examination and assessment of performance of such heuristics. The analysis of coloring methods may take either a quantity or quality oriented form. It may concern computational complexity and the closely connected algorithm run time, or the quality of generated solutions. The analysis of the quality of graph coloring methods is usually conducted for graphs of order tending to infinity. The performance guarantee enables the assessment of the behavior of an algorithm for the worst-case input data of a given size. Such analysis is usually of an asymptotic nature and can be regarded as an indicator of the outcome of graph coloring for graphs of order n → ∞. Unfortunately, in the case of some of the more complex methods analysis of algorithm performance may turn out extremely difficult. What is more, even a known performance guarantee does not describe the behavior of the algorithm in the average case. Neither does the performance guarantee correspond to the behavior of the coloring method for relatively small graphs, which may undergo theoretical analysis. Consequently it may not be used to determine all the classes of graphs colored in a suboptimal way by a given method. When judging the performance of heuristic methods, the relevant characteristics of a method include not only computational complexity and accuracy of generated solutions for large values of n, but also the level of complexity of graphs for which the method leads to suboptimal solutions. mechanism of a particular heuristic proves to be helpful. The first hard-to-color graphs were found in the 1990‘s. Unfortunately, the development and refinement of coloring methods and, most of all, their rising level of complexity make analysis more and more arduous. Therefore the usage of computer techniques to find the weak point of coloring algorithms appears to be a natural solution.

An exhaustive search of the space of all colorings generated by a particular method gives absolute certainty of detecting any number of hard-to-color graphs for the considered method. Unfortunately, the duration time of such an operation may turn out a serious obstacle. One has to realize that even for a relatively small number of vertices n the number of possible graphs spanned on these vertices is very nearly astronomical, as it is expressed by a super-exponential function of n. In addition, for a single graph there may exist numerous and essentially different legal implementations of a given method, yielding different colorings, which drastically increases the size of the search space. Hard-to-color graphs discovered by means of computer methods later undergo intensive theoretical research, aiming at the verification of the correctness of the obtained results. The theoretical search and analysis of hard-to-color graphs enable the estimation of the anticipated effectiveness of the method and — what is most important — often suggest improvements which contribute to the development of new, more effective graph coloring methods. Furthermore, they enable the comparison of graph coloring algorithms, as more effective algorithms as a rule have larger hard-to-color graphs than less optimal algorithms. Many new algorithms for heuristic graph coloring use different approaches, often determined by the specific features of the problem, which leads to serious difficulties in testing the effectiveness of such algorithms. On the whole, there are two general, sensible approaches to testing algorithms, and they do not rule each other out. The first approach relies on the choice of such families of hard-to-color graphs which are connected with dedicated coloring methods used for certain classes of problems, or such families of hard-to-color graphs which are connected with characteristic input data sets. The second approach is based on a separate search and analysis of hard-to-color graphs for entire families of coloring methods. Such graphs are called benchmarks. Likewise, we define weak benchmarks as slightly hard-to-color graphs for many algorithms. method on general graphs or on a class of large graphs which are difficult for other methods, we can obtain an estimate of the method‘s behavior for such graphs. It is possible to measure the percentage of graphs from such a class which are colored sub-optimally and judge how inaccurate the generated colorings may turn out. Classical graph coloring or, more precisely, the task of finding an optimal vertex-coloring as defined in the classical sense, is an NP-hard problem that is — informally speaking — a problem with no known polynomial solution. The fact, that even the task of estimating the value of the graph classical chromatic number by means of any k-relative or k-absolute approximation algorithm is NP-hard, may be regarded as some measure of the true difficulty of the analyzed problem. Moreover, classical coloring remains NP-hard even in spite of strong restrictions imposed on the class of graphs which are taken into consideration and on the number of colors used. Quite recently a proof of the NP-hardness of 4-coloring of tripartite graphs was presented. The problem of determining whether a given planar graph with a degree not exceeding 4 is 3-colorable, is also NP-hard. On the other hand, there exist entire classes of graphs whose chromatic number can be given through a simple formula, or whose optimal coloring can be determined in polynomial time (interval graphs, for instance, fall into this category. In order to determine a simple bound on the graph chromatic number in the general case, it is sufficient to notice that the chromatic number of an empty graph is equal to 1, while the chromatic number of a complete graph of order n equals n. Apart from bounds for the chromatic number of general graphs, there exist certain trivial or nontrivial bounds for the chromatic number of particular classes of graphs. The most famous result in the theory of graph coloring, namely the 4- color theorem stating that any planar graph can be colored with four colors, is an appropriate example.

The high computational complexity of the graph coloring problem necessitates the use of heuristic approximation methods for the determination of suboptimal solutions in polynomial time. Color interchange is a relatively simple method of improving the effectiveness of any sequential coloring algorithm. The idea of coloring the edges of a graph has been investigated for many years due to the large number of its practical applications. The classical The problem of coloring the edges of a graph belongs to the family of NP-hard problems, just as the problem of vertex-coloring. In fact, the task of determining an optimal edge coloring of graph G can be solved by finding an optimal vertex-coloring of a graph known as the line graph of G. The line graph of graph G, denoted by L(G), is a graph in which every vertex corresponds to exactly one edge of G, and any two vertices of graph L(G) are adjacent if and only if the corresponding edges of graph G are adjacent. Very strong bounds for the chromatic index are known despite the high computational complexity of the edge-coloring problem. Because the determination of the value of the chromatic index remains an NP-hard problem despite the strength of known bounds, and — more importantly — because numerous applications of edge-coloring require not only the value of the chromatic index but also an assignment of colors, effective heuristics solving the problem of edge-coloring remain indispensable.

Overall, there are two different approaches to determining suboptimal edge-colorings of a graph. The first approach relies on the use of a wide variety of heuristic methods for coloring line graphs. The alternative approach concentrates on dedicated methods, designed especially for the edge-coloring of graphs. The naive (greedy) edge-coloring algorithm as well as Vizing‘s widely used method belong to the latter group.

1. Boris Aronov, Mark de Berg, and Chris Gray (2015). Ray shooting and intersection searching amidst fat convex polyhedra in 3-space. Computational Geometry: Theory and Applications, 41: pp. 68–76, 5.2 2. Umut A. Acar, Benoˆıt Hudson, Gary L. Miller, and Todd Phillips (2014). SVR: Practical engineering of a fast 3D meshing algorithm. In Proc. 16th International Meshing Roundtable, pages 45–62. 4.15, 7.7 3. Ivo Babuˇska and A. K. Aziz (2013). On the Angle Condition in the Finite Element Method. SIAM Journal on Numerical Analysis, 13(2): pp. 214–226, April 2013. 1.1 4. Alexander Barvinok (2012). A Course in Convexity. American Mathematical Society. Christian Sohler (2015). Average case complexity of Voronoi diagrams of n sites from the unit cube. In EWCG: European Workshop Comput. Geom., pages 167–170. 6. Marshall Wayne Bern, David Eppstein, and John Russell Gilbert (1994). Provably good mesh generation. J. Computer & Systems Sciences, 48(3): pp. 384–409, June 1994. Special issue for 31st FOCS. 4.2 7. M. Bern, D. Eppstein, and S.H. Teng (2014). Parallel construction of quadtrees and quality triangulations. International Journal of Computational Geometry and Applications (IJCGA), 9(6): pp. 517–532. 4.2 8. Mikhail Belkin and Partha Niyogi (2011). Laplacian eigenmaps and spectral techniques for embedding and clustering. In Advances in Neural Information Processing Systems 14, pages 585–591. 9. Gunnar Carlsson (2009). Topology and data. Bull. Amer. Math. Soc., 46: pp. 255–308.

Research Scholar, Mother Hood University, Roorkee, Dehradun