<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

Data publikacji: 31 gru 2018

Zakres stron: 137 - 157

Otrzymano: 23 lut 2018

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

Słowa kluczowe
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

Data publikacji: 31 gru 2018

Zakres stron: 137 - 157

Otrzymano: 23 lut 2018

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

Słowa kluczoweclique 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.

Słowa kluczowe
clique number, chromatic number, maximum clique legal coloring of the nodes, greedy coloring