Estimating clique size by coloring the nodes of auxiliary graphs
| 31. Dez. 2018
Über diesen Artikel
Online veröffentlicht: 31. Dez. 2018
Seitenbereich: 137 - 157
Eingereicht: 23. Feb. 2018
DOI: https://doi.org/10.2478/ausi-2018-0008
Schlüsselwörter
© 2018 Sándor Szabó, published by Sciendo
This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 3.0 License.
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.