Clique number estimate based on coloring of the nodes
Abstract
We will describe an algorithm to establish an upper estimate of the clique number of a given graph. The procedure is based on greedy legal coloring of the nodes. In order to assess the performance of the procedure we carried out a large scale numerical experiment.
2020 Mathematics Subject Classification:
05C15, 05B45, 52C22Keywords
clique number, chromatic number, maximum clique, greedy coloring, clique number estimates
Author Details
Sándor Szabó
Institute of Mathematics and Informatics
University of Pécs
Ifjúság u. 6
7624 Pécs, Hungary
e-mail: sszabo7@hotmail.com
Bogdán Zavalnij
Alfréd Rényi Institute of Mathematics
Budapest, Hungary
e-mail: bogdan@renyi.hu
References
- Ü. V. Çatalyürek, J. Feo, A. H. Gebremedhin, M. Halappanavar, A. Pothen. Graph coloring algorithms for multi-core and massively multithreaded architectures. Parallel Comput. 38, sl 10–11 (2012), 576–594.
- F. T. Leighton. A graph coloring algorithm for large scheduling problems. J. Res. Nat. Bur. Standards 84, 6 (1979), 489–506.
- D. W. Matula, G. Marble, J. Isaacson. Graph coloring algorithms. In: Graph Theory and Computing (ed. R. Read) New York, Academic Press, 1972, 109–122.
- J. Mycielski. Sur le coloriage des graphes. Colloq. Math. 3 (1955), 161–162 (in French).
- P. R. J. Östergård. A fast algorithm for the maximum clique problem. Sixth Twente Workshop on Graphs and Combinatorial Optimization (Enschede, 1999). Discrete Appl. Math. 120, 1–3 (2002), 197–207.
- C. H. Papadimitriou. Computational Complexity. Reading, MA, Addison-Wesley Publishing Company, Inc., 1994.
- N. J. A. Sloane. Challenge Problems: Independent Sets in Graphs. https://oeis.org/a265032.html
- S. Szabó, Monotonic matrices and clique search in graphs, Ann. Univ. Sci. Budapest., Sect. Comput. 41 (2013), 307–322.
- S. Szabó, B. Zaválnij. Reducing graph coloring to clique search, Asia Pacific Journal of Mathematics 3 (2016), 64–85, http://apjm.apacific.org/PDFs/3-1-64-85.pdf.
- E. W. Weisstein. Monotonic Matrix. In: MathWorld–A Wolfram Web Resource. http://mathworld.wolfram.com/MonotonicMatrix.html.