A note on fractional covers of a graph
| Autor: | Gauci, John Baptist, Zerafa, Jean Paul |
|---|---|
| Rok vydání: | 2020 |
| Předmět: | |
| Zdroj: | Art Discrete Appl. Math. 6(1), P1.06 (2023) |
| Druh dokumentu: | Working Paper |
| DOI: | 10.26493/2590-9770.1398.fe9 |
| Popis: | 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 $G_2$ is a homomorphic image of a simple graph $G_1$, then the fractional cover number defined on the $(k+1)$-clique-free subgraphs of $G_1$ is bounded above by the corresponding number of $G_2$. 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. Comment: 8 pages |
| Databáze: | arXiv |
| Externí odkaz: |
|