Estimating clique size by coloring the nodes of auxiliary graphs

Sándor Szabó

doi:10.2478/ausi-2018-0008

Abstract

It is a common practice to find upper bound for clique number via legal coloring of the nodes of the graph. We will point out that with a little extra work we may lower this bound. Applying this procedure to a suitably constructed auxiliary graph one may further improve the clique size estimate of the original graph.

References

[1] E. Balas, J. Xue, Weighted and unweighted maximum clique algorithms with upper bounds from fractional coloring, Algorithmica15 (1996), 397–412. ⇒13810.1007/BF01955041
Search in Google Scholar Back to article
[2] I. M. Bomze, M. Budinich, P. M. Pardalos, M. Pelillo, The Maximum Clique Problem, Handbook of Combinatorial Optimization Vol. 4, Kluwer Academic Publisher, 1999. ⇒13710.1007/978-1-4757-3023-4_1
Search in Google Scholar Back to article
[3] D. Brélaz, New methods to color the vertices of a graph, Communications of the ACM22 (1979), 251–256. ⇒138, 15510.1145/359094.359101
Search in Google Scholar Back to article
[4] R. Carraghan, P. M. Pardalos, An exact algorithm for the maximum clique problem, Operation Research Letters9 (1990), 375–382. ⇒13710.1016/0167-6377(90)90057-C
Search in Google Scholar Back to article
[5] M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-completeness, Freeman, New York, 2003. ⇒138
Search in Google Scholar Back to article
[6] J. Hasselberg, P. M. Pardalos, and G. Vairaktarakis, Test case generators and computational results for the maximum clique problem, Journal of Global Optimization3 (1993), 463–482. ⇒137, 15510.1007/BF01096415
Search in Google Scholar Back to article
[7] J. Konc and D. Janežič, An improved branch and bound algorithm for the maximum clique problem, MATCH Communications in Mathematical and Computer Chemistry58 (2007), 569–590. ⇒138
Search in Google Scholar Back to article
[8] D. Kumlander, Some Practical Algorithms to Solve the Maximal Clique Problem, PhD. Thesis, Tallin University of Technology, 2005. ⇒138
Search in Google Scholar Back to article
[9] F. T. Leighton, A graph coloring algorithm for large scheduling problems, Journal of Research of National Bureau of Standards84 (1979), 489–506. ⇒13810.6028/jres.084.024
Search in Google Scholar Back to article
[10] J. Mycielski, Sur le coloriage des graphes, Colloq. Math.3 (1955), 161–162. ⇒15010.4064/cm-3-2-161-162
Search in Google Scholar Back to article
[11] P. R. J.Östergård, A fast algorithm for the maximum clique problem, Discrete Applied Mathematics120 (2002), 197–207. ⇒13810.1016/S0166-218X(01)00290-6
Search in Google Scholar Back to article
[12] P. Prosser, Exact algorithms for maximum clique: A computational study, Algorithms5 (2012), 545–587. ⇒13710.3390/a5040545
Search in Google Scholar Back to article
[13] P. San Segundo, C. Tapia, Relaxed approximate coloring in exact maximum clique search, Computers and Operations Research.44 (2014), 185–192. ⇒13810.1016/j.cor.2013.10.018
Search in Google Scholar Back to article
[14] S. Szabó, Monotonic matrices and clique search in graphs, Annales Univ. Sci. Budapest., Sect. Computatorica41 (2013), 307–322. ⇒155
Search in Google Scholar Back to article
[15] E. Tomita and T. Seki, An efficient branch-and-bound algorithm for finding a maximum clique, Lecture Notes in Computer Science2631 (2003), 278–289. ⇒13810.1007/3-540-45066-1_22
Search in Google Scholar Back to article
[16] D. R. Wood, An algorithm for finding a maximum clique in a graph, Operations Research Letters21 (1997), 211–217. ⇒13810.1016/S0167-6377(97)00054-0
Search in Google Scholar Back to article

Estimating clique size by coloring the nodes of auxiliary graphs

Abstract

Paradigm

My account