1-Subdivisions, the Fractional Chromatic Number and the Hall Ratio

Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F20%3A10437056" target="_blank" >RIV/00216208:11320/20:10437056 - isvavai.cz</a>
Result on the web
<a href="https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=vCQ5MJzYe0" target="_blank" >https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=vCQ5MJzYe0</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1007/s00493-020-4223-9" target="_blank" >10.1007/s00493-020-4223-9</a>

Result language
angličtina
Original language name
1-Subdivisions, the Fractional Chromatic Number and the Hall Ratio
Original language description
The Hall ratio of a graph G is the maximum of |V(H)|/α(H) over all subgraphs H of G. It is easy to see that the Hall ratio of a graph is a lower bound for the fractional chromatic number. It has been asked whether conversely, the fractional chromatic number is upper bounded by a function of the Hall ratio. We answer this question in negative, by showing two results of independent interest regarding 1-subdivisions (the 1-subdivision of a graph is obtained by subdividing each edge exactly once). For every c > 0, every graph of sufficiently large average degree contains as a subgraph the 1-subdivision of a graph of fractional chromatic number at least c. For every d > 0, there exists a graph G of average degree at least d such that every graph whose 1-subdivision appears as a subgraph of G has Hall ratio at most 18. We also discuss the consequences of these results in the context of graph cl
Czech name
—
Czech description
—

Type
J<sub>imp</sub> - Article in a specialist periodical, which is included in the Web of Science database
CEP classification
—
OECD FORD branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Project
Result was created during the realization of more than one project. More information in the Projects tab.
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Publication year
2020
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Similar results(10)