A note on fractional covers of a graph

Authors

DOI:

https://doi.org/10.26493/2590-9770.1398.fe9

Keywords:

fractional chromatic number, fractional cover, Kneser graph, n-colouring, a:b-colouring

Abstract

A fractional colouring of a graph G is a function that assigns a non-negative real value to all possible colour-classes of G containing any vertex of G, such that the sum of these values is at least one for each vertex. The fractional chromatic number is the minimum sum of the values assigned by a fractional colouring over all possible such colourings of G. Introduced by Bosica and Tardif, fractional covers are an extension of fractional colourings whereby the real-valued function acts on all possible subgraphs of G belonging to a given class of graphs. The fractional chromatic number turns out to be a special instance of the fractional cover number. In this work we investigate fractional covers acting on (k+1)-clique-free subgraphs of G which, although sharing some similarities with fractional covers acting on k-colourable subgraphs of G, they exhibit some peculiarities. We first show that if a simple graph G2 is a homomorphic image of a simple graph G1, then the fractional cover number defined on the (k+1)-clique-free subgraphs of G1 is bounded above by the corresponding number of G2. We make use of this result to obtain bounds for the associated fractional cover number of graphs that are either n-colourable or a  :  b-colourable.

Published

2022-10-04

Issue

Section

Articles