<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

Publicado en línea: 08 jul 2021

Páginas: 122 - 133

Recibido: 01 abr 2021

Aceptado: 16 may 2021

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

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

Publicado en línea: 08 jul 2021

Páginas: 122 - 133

Recibido: 01 abr 2021

Aceptado: 16 may 2021

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

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

Palabras clave
clique and chromatic numbers, fractional chromatic number, integer programming