Polynomial bounds for centered colorings on proper minor-closed graph classes

DOI10.1016/j.jctb.2021.06.002zbMath1490.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)

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)

Related Items

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, 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, Empirical Evaluation of Approximation Algorithms for Generalized Graph Coloring and Uniform Quasi-wideness, Erdös--Hajnal Properties for Powers of Sparse Graphs

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