<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

Publié en ligne: 08 juil. 2021

Pages: 122 - 133

Reçu: 01 avr. 2021

Accepté: 16 mai 2021

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

Mots clés
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

Publié en ligne: 08 juil. 2021

Pages: 122 - 133

Reçu: 01 avr. 2021

Accepté: 16 mai 2021

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

Mots clésclique 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.

Mots clés
clique and chromatic numbers, fractional chromatic number, integer programming