1-Subdivisions, the Fractional Chromatic Number and the Hall Ratio
| Autor: | Zdenĕk Dvořák, Hehui Wu, Patrice Ossona de Mendez |
|---|---|
| Přispěvatelé: | Centre d'Analyse et de Mathématique sociales (CAMS), École des hautes études en sciences sociales (EHESS)-Centre National de la Recherche Scientifique (CNRS) |
| Jazyk: | angličtina |
| Rok vydání: | 2020 |
| Předmět: |
business.industry
010102 general mathematics 0102 computer and information sciences 01 natural sciences Upper and lower bounds Graph Combinatorics Computational Mathematics 010201 computation theory & mathematics Bounded function [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO] Bounded expansion Discrete Mathematics and Combinatorics Chromatic scale 0101 mathematics business ComputingMilieux_MISCELLANEOUS Subdivision Mathematics |
| Zdroj: | Combinatorica Combinatorica, Springer Verlag, 2020, ⟨10.1007/s00493-020-4223-9⟩ |
| ISSN: | 0209-9683 1439-6912 |
| DOI: | 10.1007/s00493-020-4223-9⟩ |
| Popis: | 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). We also discuss the consequences of these results in the context of graph classes with bounded expansion. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full text from SpringerLink