Estimating clique size via discarding subgraphs

Sandor Szabo, Bogdan Zavalnij


The paper will present a method to establish an upper bound on the clique number of a
given finite graph. In order to evaluate the proposed algorithm in practice we carry out
a large scale numerical experiment.

Full Text:



E. Balas and J. Xue,

emph{Weighted and unweighted maximum clique algorithms with

upper bounds from fractional coloring,}

Algorithmica 15 (1996), pp.~397--412.

I. M. Bomze, M. Budinich, P. M. Pardalos and

M. Pelillo, emph{The Maximum Clique Problem, Handbook of

Combinatorial Optimization Vol. 4,} Kluwer Academic Publisher,

B. Borchers, emph{CSDP, A C Library for Semidefinite

Programming,} Optimization Methods and Software,

(1) (1999), pp.~613--623.

B. Borchers and J. G. Young. emph{Implementation of a primal-dual method

for SDP on a shared memory parallel architecture,} Computational

Optimization and Applications 37(3), (2007) pp.~355--369.

A. B'ota and M. Kr'esz. emph{A High Resolution Clique-based

Overlapping Community Detection Algorithm for Small-world Networks.}

Informatica, 39(2). (2015).

D. Brelaz,

emph{New methods to color the vertices of a graph,}

Communications of the ACM, 22 (1979), pp.~251--256.

J. C. Culberson, emph{Iterated Greedy Graph Coloring and the

Difficulty Landscape,} Technical Report, University of

Alberta, 1992.

C. Elphick and P. Wocjan,

emph{An inertial lower bound for the chromatic number of a graph,}

arXiv:1605.01978 (2016) url{}

M. R. Garey and D. S. Johnson,

emph{Computers and Intractability: A Guide to the Theory of NP-completeness,}

Freeman, New York, 2003.

F. Harary, emph{Graph Theory,} Addison-Wesley, 1969.

J. Hasselberg, P. M. Pardalos, and G. Vairaktarakis,

emph{Test case generators and computational results for the maximum clique


Journal of Global Optimization 3 (1993), pp.~463--482.


D. Kumlander,

emph{Some Practical Algorithms to Solve the Maximal Clique Problem,}

PhD. Thesis, Tallin University of Technology, 2005.

S. Lamm, P. Sanders, C. Schulz, D. Strash, R.

F. Werneck. Finding Near-Optimial Independent Sets at

Scale. {it Proceedings of the 16th Meeting on Algorithm Engineering and

Experimentation (ALENEX'16).} 2016.

F. T. Leighton,

emph{A graph coloring algorithm for large scheduling problems,}

Journal of Research of National Bureau of Standards

(1979), pp.~489--506.

L. Lovasz, emph{On the Shannon Capacity of a Graph,}

IEEE Transactions on Information Theory, Volume 25 Issue 1,

January 1979 pp.~1--7.

P.R.J. "Ostergaa rd and A. P"oll"anen, emph{New Results on Tripod

Packings.} Discrete Comput Geom 61, 271--284 (2019).

C. H. Papadimitriou,

emph{Computational Complexity,}

Addison-Wesley Publishing Company, Inc., Reading, MA 1994.

N. J. A. Sloane,

emph{Challenge Problems: Independent Sets in Graphs,}


S. Stahl, emph{$n$-Tuple colorings and associated

graphs.} Journal of Combinatorial Theory, Series B Volume 20, Issue

, April 1976, pp.~185--203.

S. Szab'o

emph{Monotonic matrices and clique search in graphs,}

Annales Univ. Sci. Budapest., Sect. Comp.

(2013), pp.~307--322.

S. Szab'o and B. Zav'alnij, emph{Reducing graph

coloring to clique search,} Asia Pacific Journal of Mathematics, 1

(2016), pp.~64--85.

S. Szab'o and B. Zav'alnij, A different

approach to maximum clique search. emph{20th International Symposium on

Symbolic and Numeric Algorithms for Scientific Computing

(SYNASC2018)} pp.~310--316.

S. Szab'o and B. Zav'alnij, emph{Reducing

hypergraph coloring to clique search.} Discrete Applied Mathematics,

(2019), pp.~196--207.

Q. Wu and J-K. Hao, emph{A review on algorithms for maximum

clique problems,} European Journal of Operational Research.

Volume 242, Issue 3, 1 May 2015, pp.~693--709.


Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.