Improved Bounds for Centered Colorings
From MaRDI portal
Publication:5162872
DOI10.19086/aic.27351zbMath1478.05050arXiv1907.04586OpenAlexW2958527737MaRDI QIDQ5162872
Piotr Micek, Stefan Felsner, Michał Dębski, Felix Schröder
Publication date: 5 November 2021
Published in: Advances in Combinatorics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1907.04586
Analysis of algorithms and problem complexity (68Q25) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (9)
Improved bounds for weak coloring numbers ⋮ An improved planar graph product structure theorem ⋮ A General Framework for Hypergraph Coloring ⋮ Separating layered treewidth and row treewidth ⋮ Improved product structure for graphs on surfaces ⋮ Graph colorings with restricted bicolored subgraphs: I. Acyclic, star, and treewidth colorings ⋮ Shallow Minors, Graph Products, and Beyond-Planar Graphs ⋮ The product structure of squaregraphs ⋮ Graph product structure for non-minor-closed classes
Cites Work
- Characterisations and examples of graph classes with bounded expansion
- Nonrepetitive colorings of graphs of bounded tree-width
- Graph minors. XVI: Excluding a non-planar graph
- Polynomial bounds for centered colorings on proper minor-closed graph classes
- Polynomial treedepth bounds in linear colorings
- Grad and classes with bounded expansion. I: Decompositions
- On nowhere dense graphs
- Tree-depth, subgraph coloring and homomorphism bounds
- A fast algorithm for the product structure of planar graphs
- Star coloring of graphs
- Two lower bounds for $p$-centered colorings
- A constructive proof of the general lovász local lemma
- New approach to nonrepetitive sequences
- On Space Efficiency of Algorithms Working on Structural Decompositions of Graphs
- Planar Graphs Have Bounded Queue-Number
- Improved bounds for centered colorings
- Structure Theorem and Isomorphism Test for Graphs with Excluded Topological Subgraphs
- Layout of Graphs with Bounded Tree-Width
- Testing first-order properties for subclasses of sparse graphs
This page was built for publication: Improved Bounds for Centered Colorings
