<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

Online veröffentlicht: 08. Juli 2021

Seitenbereich: 122 - 133

Eingereicht: 01. Apr. 2021

Akzeptiert: 16. Mai 2021

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

Schlüsselwörter
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

Online veröffentlicht: 08. Juli 2021

Seitenbereich: 122 - 133

Eingereicht: 01. Apr. 2021

Akzeptiert: 16. Mai 2021

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

Schlüsselwörterclique 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.

Schlüsselwörter
clique and chromatic numbers, fractional chromatic number, integer programming