<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

Published Online: Dec 31, 2018

Page range: 137 - 157

Received: Feb 23, 2018

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

Keywords
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

Published Online: Dec 31, 2018

Page range: 137 - 157

Received: Feb 23, 2018

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

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

Keywords
clique number, chromatic number, maximum clique legal coloring of the nodes, greedy coloring