<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

Published Online: Jul 08, 2021

Page range: 122 - 133

Received: Apr 01, 2021

Accepted: May 16, 2021

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

Keywords
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

Published Online: Jul 08, 2021

Page range: 122 - 133

Received: Apr 01, 2021

Accepted: May 16, 2021

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

Keywordsclique 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.

Keywords
clique and chromatic numbers, fractional chromatic number, integer programming