Publication:1984513

DOI10.1137/1.9781611975482.91zbMath1490.05082arXiv1807.03683OpenAlexW3173204516MaRDI QIDQ1984513

Michał Pilipczuk, Sebastian Siebertz

Publication date: 16 September 2021

Published in: Journal of Combinatorial Theory. Series B, Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Abstract: For $pin mathbb{N}$, a coloring $lambda$ of the vertices of a graph $G$ is {em{$p$-centered}} if for every connected subgraph~$H$ of $G$, either $H$ receives more than $p$ colors under $lambda$ or there is a color that appears exactly once in $H$. In this paper, we prove that every $K_t$-minor-free graph admits a $p$-centered coloring with $mathcal{O}(p^{g(t)})$ colors for some function $g$. In the special case that the graph is embeddable in a fixed surface $Sigma$ we show that it admits a $p$-centered coloring with $mathcal{O}(p^{19})$ colors, with the degree of the polynomial independent of the genus of $Sigma$. This provides the first polynomial upper bounds on the number of colors needed in $p$-centered colorings of graphs drawn from proper minor-closed classes, which answers an open problem posed by Dvov{r}{'a}k. As an algorithmic application, we use our main result to prove that if $mathcal{C}$ is a fixed proper minor-closed class of graphs, then given graphs $H$ and $G$, on $p$ and $n$ vertices, respectively, where $Gin mathcal{C}$, it can be decided whether $H$ is a subgraph of $G$ in time $2^{mathcal{O}(plog p)}cdot n^{mathcal{O}(1)}$ and space $n^{mathcal{O}(1)}$.

Full work available at URL: https://arxiv.org/abs/1807.03683

zbMATH Keywords

subgraph isomorphismsparse graphsstructural graph theorycentered colorings\(K_t\)-minor-free graph

Mathematics Subject Classification ID

Structural characterization of families of graphs (05C75) Coloring of graphs and hypergraphs (05C15) Graph minors (05C83) Graph algorithms (graph-theoretic aspects) (05C85) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Density (toughness, etc.) (05C42)

Cites Work

• Unnamed Item
• Unnamed Item
• Colouring graphs with bounded generalized colouring number
• Graph minors. XVI: Excluding a non-planar graph
• Optimally cutting a surface into a disk
• Orderings on graphs and game coloring number
• Excluding any graph as a minor allows a low tree-width 2-coloring
• Approximation algorithms via contraction decomposition
• Polynomial bounds for centered colorings on proper minor-closed graph classes
• Grad and classes with bounded expansion. I: Decompositions
• On nowhere dense graphs
• Tree-depth, subgraph coloring and homomorphism bounds
• Local tree-width, excluded minors, and approximation algorithms
• Planar Subgraph Isomorphism Revisited
• A Separator Theorem for Planar Graphs
• Color-coding
• Subgraph Isomorphism in Planar Graphs and Related Problems
• Coloring and Covering Nowhere Dense Graphs
• Subexponential Time Algorithms for Embedding H-Minor Free Graphs
• On Space Efficiency of Algorithms Working on Structural Decompositions of Graphs
• First-Order Interpretations of Bounded Expansion Classes
• Parameterized circuit complexity of model-checking on sparse structures
• Improved bounds for centered colorings
• Object location using path separators
• Testing first-order properties for subclasses of sparse graphs
• Contraction decomposition in h-minor-free graphs and algorithmic applications
• A simpler algorithm and shorter proof for the graph minor decomposition
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• A Simple Algorithm for the Graph Minor Decomposition − Logic meets Structural Graph Theory–
• On the generalised colouring numbers of graphs that exclude a fixed minor

Related Items (24)

Improved bounds for weak coloring numbers ⋮ Twin-width II: small classes ⋮ An improved planar graph product structure theorem ⋮ A fast algorithm for the product structure of planar graphs ⋮ Two lower bounds for $p$-centered colorings ⋮ A \(p\)-centered coloring for the grid using \(O(p)\) colors ⋮ Sparse universal graphs for planarity ⋮ Shallow Minors, Graph Products, and Beyond-Planar Graphs ⋮ Hamiltonian Cycle Parameterized by Treedepth in Single Exponential Time and Polynomial Space ⋮ Graph product structure for non-minor-closed classes ⋮ Graph theory. Abstracts from the workshop held January 2--8, 2022 ⋮ On fractional fragility rates of graph classes ⋮ Bounds on half graph orders in powers of sparse graphs ⋮ Clustering powers of sparse graphs ⋮ Product structure of graphs with an excluded minor ⋮ Treelike decompositions for transductions of sparse graphs ⋮ Polynomial bounds for centered colorings on proper minor-closed graph classes ⋮ Improved Bounds for Centered Colorings ⋮ A \(2^{O(k)}n\) algorithm for \(k\)-cycle in minor-closed graph families ⋮ Unnamed Item ⋮ Twin-width. III: Max independent set, min dominating set, and coloring ⋮ Graph product structure for \(h\)-framed graphs ⋮ Empirical Evaluation of Approximation Algorithms for Generalized Graph Coloring and Uniform Quasi-wideness ⋮ Erdös--Hajnal Properties for Powers of Sparse Graphs

This page was built for publication: Polynomial bounds for centered colorings on proper minor-closed graph classes