Contributors: Faculty of Mathematics and Computer Science of the Jagiellonian University; Uniwersytet Jagielloński w Krakowie = Jagiellonian University = Université Jagellon de Cracovie (UJ); Graphes, Algorithmes et Combinatoire - LISN (GALaC); Laboratoire Interdisciplinaire des Sciences du Numérique (LISN); Institut National de Recherche en Informatique et en Automatique (Inria)-CentraleSupélec-Université Paris-Saclay-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-CentraleSupélec-Université Paris-Saclay-Centre National de la Recherche Scientifique (CNRS)-Algorithmes, Apprentissage et Calcul (AAC); Institut National de Recherche en Informatique et en Automatique (Inria)-CentraleSupélec-Université Paris-Saclay-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-CentraleSupélec-Université Paris-Saclay-Centre National de la Recherche Scientifique (CNRS); Combinatorics, Optimization and Algorithms for Telecommunications (COATI); Inria Sophia Antipolis - Méditerranée (CRISAM); Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED); Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S); Université Nice Sophia Antipolis (1965 - 2019) (UNS)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UniCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UniCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S); Université Nice Sophia Antipolis (1965 - 2019) (UNS)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UniCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UniCA); ANR-19-CE48-0013,DIGRAPHS,Digraphes(2019)
Abstract: International audience ; We study the growth rate of weak coloring numbers of graphs excluding a fixed graph as a minor. Van den Heuvel et al. (European J. of Combinatorics, 2017) showed that for a fixed graph $X$, the maximum $r$-th weak coloring number of $X$-minor-free graphs is polynomial in $r$. We determine this polynomial up to a factor of $\mathcal{O}(r \log r)$. Moreover, we tie the exponent of the polynomial to a structural property of $X$, namely, $2$-treedepth. As a result, for a fixed graph $X$ and an $X$-minor-free graph $G$, we show that $\mathrm{wcol}_r(G)= \mathcal{O}(r^{\mathrm{td}(X)-1}\mathrm{log}\ r)$, which improves on the bound $\mathrm{wcol}_r(G) = \mathcal{O}(r^{g(\mathrm{td}(X))})$ given by Dujmović et al. (SODA, 2024), where $g$ is an exponential function. In the case of planar graphs of bounded treewidth, we show that the maximum $r$-th weak coloring number is in $\mathcal{O}(r^2\mathrm{log}\ r$), which is best possible.
Processing Request
No Comments.