Skip to main navigation menu Skip to main content Skip to site footer

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, 52C22

Keywords

clique number, chromatic number, maximum clique, greedy coloring, clique number estimates

Full text

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

  1. Ü. 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.
  2. F. T. Leighton. A graph coloring algorithm for large scheduling problems. J. Res. Nat. Bur. Standards 84, 6 (1979), 489–506.
  3. 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.
  4. J. Mycielski. Sur le coloriage des graphes. Colloq. Math. 3 (1955), 161–162 (in French).
  5. 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.
  6. C. H. Papadimitriou. Computational Complexity. Reading, MA, Addison-Wesley Publishing Company, Inc., 1994.
  7. N. J. A. Sloane. Challenge Problems: Independent Sets in Graphs. https://oeis.org/a265032.html
  8. S. Szabó, Monotonic matrices and clique search in graphs, Ann. Univ. Sci. Budapest., Sect. Comput. 41 (2013), 307–322.
  9. 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.
  10. E. W. Weisstein. Monotonic Matrix. In: MathWorld–A Wolfram Web Resource. http://mathworld.wolfram.com/MonotonicMatrix.html.