<abstract xmlns="http://www.w3.org/1999/xhtml">

<p>The fractional chromatic number of a graph is defined as the optimum of a rather unwieldy linear program. (Setting up the program requires generating all independent sets of the given graph.) Using combinatorial arguments we construct a more manageable linear program whose optimum value provides an upper estimate for the fractional chromatic number. In order to assess the feasibility of the proposal and in order to check the accuracy of the estimates we carry out numerical experiments.</p>
</abstract>

The fractional chromatic number of a graph is defined as the optimum of a rather unwieldy linear program. (Setting up the program requires generating all independent sets of the given graph.) Using combinatorial arguments we construct a more manageable linear program whose optimum value provides an upper estimate for the fractional chromatic number. In order to assess the feasibility of the proposal and in order to check the accuracy of the estimates we carry out numerical experiments.

Estimating the fractional chromatic number of a graph

Acta Universitatis Sapientiae, Informatica

This work is licensed under the Creative Commons Attribution 4.0 International License.

{"article-title":"Estimating the fractional chromatic number of a graph"}

The fractional chromatic number of a graph is defined as the optimum of a rather unwieldy linear program. (Setting up the program requires generating all...

Estimating the fractional chromatic number of a graph

Pubblicato online: 08 lug 2021

Pagine: 122 - 133

Ricevuto: 01 apr 2021

Accettato: 16 mag 2021

DOI: https://doi.org/10.2478/ausi-2021-0006

Parole chiave
clique and chromatic numbers, fractional chromatic number, integer programming

© 2021 Sándor Szabó, published by Sciendo

This work is licensed under the Creative Commons Attribution 4.0 International License.

Estimating the fractional chromatic number of a graph

Pubblicato online: 08 lug 2021

Pagine: 122 - 133

Ricevuto: 01 apr 2021

Accettato: 16 mag 2021

DOI: https://doi.org/10.2478/ausi-2021-0006

Parole chiaveclique and chromatic numbers, fractional chromatic number, integer programming

© 2021 Sándor Szabó, published by Sciendo

This work is licensed under the Creative Commons Attribution 4.0 International License.

Parole chiave
clique and chromatic numbers, fractional chromatic number, integer programming