<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

Publicado en línea: 31 dic 2018

Páginas: 137 - 157

Recibido: 23 feb 2018

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

Palabras clave
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

Publicado en línea: 31 dic 2018

Páginas: 137 - 157

Recibido: 23 feb 2018

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

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

Palabras clave
clique number, chromatic number, maximum clique legal coloring of the nodes, greedy coloring