<abstract xmlns="http://www.w3.org/1999/xhtml"><p>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.</p></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.

Estimating clique size by coloring the nodes of auxiliary graphs

Acta Universitatis Sapientiae, Informatica

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 3.0 License.

{"article-title":"Estimating clique size by coloring the nodes of auxiliary graphs"}

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...

Estimating clique size by coloring the nodes of auxiliary graphs

Publié en ligne: 31 déc. 2018

Pages: 137 - 157

Reçu: 23 févr. 2018

DOI: https://doi.org/10.2478/ausi-2018-0008

Mots clés
clique number, chromatic number, maximum clique legal coloring of the nodes, greedy coloring

© 2018 Sándor Szabó, published by Sciendo

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 3.0 License.

Estimating clique size by coloring the nodes of auxiliary graphs

Publié en ligne: 31 déc. 2018

Pages: 137 - 157

Reçu: 23 févr. 2018

DOI: https://doi.org/10.2478/ausi-2018-0008

Mots clésclique number, chromatic number, maximum clique legal coloring of the nodes, greedy coloring

© 2018 Sándor Szabó, published by Sciendo

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 3.0 License.

Mots clés
clique number, chromatic number, maximum clique legal coloring of the nodes, greedy coloring