Tree-depth, subgraph coloring and homomorphism bounds

DOI10.1016/j.ejc.2005.01.010zbMath1089.05025OpenAlexW2052210031MaRDI QIDQ2493118

Patrice Ossona de Mendez, Jaroslav Nešetřil

Publication date: 9 June 2006

Published in: European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ejc.2005.01.010

zbMATH Keywords

decomposition chromatic number graph partitions minor closed class

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph minors (05C83)

Related Items

A polynomial excluded-minor approximation of treedepth ⋮ List rankings and on-line list rankings of graphs ⋮ Tree-Depth and the Formula Complexity of Subgraph Isomorphism ⋮ Structure and Power: an Emerging Landscape ⋮ Tree-depth and vertex-minors ⋮ Unique-Maximum and Conflict-Free Coloring for Hypergraphs and Tree Graphs ⋮ Bridge-Depth Characterizes which Minor-Closed Structural Parameterizations of Vertex Cover Admit a Polynomial Kernel ⋮ Uniform Kernelization Complexity of Hitting Forbidden Minors ⋮ Some notes on bounded starwidth graphs ⋮ Chromatic numbers of exact distance graphs ⋮ On Dasgupta's hierarchical clustering objective and its relation to other graph parameters ⋮ Unnamed Item ⋮ A Note on Circular Chromatic Number of Graphs with Large Girth and Similar Problems ⋮ Distance from triviality 2.0: hybrid parameterizations ⋮ \(2\times n\) grids have unbounded anagram-free chromatic number ⋮ A tight lower bound for vertex planarization on graphs of bounded treewidth ⋮ Homomorphisms and edge-colourings of planar graphs ⋮ A fast algorithm for the product structure of planar graphs ⋮ The \(k\)-strong induced arboricity of a graph ⋮ On the Power of Tree-Depth for Fully Polynomial FPT Algorithms ⋮ Space saving by dynamic algebraization based on tree-depth ⋮ Algorithmic Applications of Tree-Cut Width ⋮ Compact representation of graphs with bounded bandwidth or treedepth ⋮ Hypertree-depth and minors in hypergraphs ⋮ Grundy Distinguishes Treewidth from Pathwidth ⋮ On the lossy kernelization for connected treedepth deletion set ⋮ Reconfiguration in bounded bandwidth and tree-depth ⋮ Structural parameters, tight bounds, and approximation for \((k, r)\)-center ⋮ Parameterized (Approximate) Defective Coloring ⋮ Thue choosability of trees ⋮ Forbidden graphs for tree-depth ⋮ On low tree-depth decompositions ⋮ A Unified Approach to Structural Limits and Limits of Graphs with Bounded Tree-Depth ⋮ Uniqueness and minimal obstructions for tree-depth ⋮ Grad and classes with bounded expansion. I: Decompositions ⋮ Grad and classes with bounded expansion. II: Algorithmic aspects ⋮ Grad and classes with bounded expansion. III: Restricted graph homomorphism dualities ⋮ Unnamed Item ⋮ On nowhere dense graphs ⋮ Polynomial graph invariants from homomorphism numbers ⋮ Finite Automata, Digraph Connectivity, and Regular Expression Size ⋮ Many Facets of Dualities ⋮ Bounds on half graph orders in powers of sparse graphs ⋮ Clustering powers of sparse graphs ⋮ Digraph width measures in parameterized algorithmics ⋮ On the tree-depth of random graphs ⋮ How many \(F\)'s are there in \(G\)? ⋮ Colouring, constraint satisfaction, and complexity ⋮ Regular partitions of gentle graphs ⋮ Colouring edges with many colours in cycles ⋮ Nonrepetitive colorings of graphs -- a survey ⋮ How to compute digraph width measures on directed co-graphs ⋮ Practical algorithms for MSO model-checking on tree-decomposable graphs ⋮ Uniform orderings for generalized coloring numbers ⋮ Classes of graphs with low complexity: the case of classes with bounded linear rankwidth ⋮ Characterisations and examples of graph classes with bounded expansion ⋮ Computing tree-depth faster than \(2^n\) ⋮ Polynomial bounds for centered colorings on proper minor-closed graph classes ⋮ On the generalised colouring numbers of graphs that exclude a fixed minor ⋮ On 1-uniqueness and dense critical graphs for tree-depth ⋮ Improved Bounds for Centered Colorings ⋮ PROVABLY SHORTER REGULAR EXPRESSIONS FROM FINITE AUTOMATA ⋮ Unnamed Item ⋮ LIFO-search: a min-max theorem and a searching game for cycle-rank and tree-depth ⋮ On low rank-width colorings ⋮ Obstructions for bounded shrub-depth and rank-depth ⋮ Whither semantics? ⋮ A distributed low tree-depth decomposition algorithm for bounded expansion classes ⋮ Parameterized complexity of length-bounded cuts and multicuts ⋮ The complexity of bicriteria tree-depth ⋮ Where First-Order and Monadic Second-Order Logic Coincide ⋮ The complexity of bicriteria tree-depth ⋮ Bounds on vertex colorings with restrictions on the union of color classes ⋮ Relating Structure and Power: Comonadic Semantics for Computational Resources ⋮ LIFO-Search on Digraphs: A Searching Game for Cycle-Rank ⋮ Faster Computation of Path-Width ⋮ Colouring games on outerplanar graphs and trees ⋮ Structurally parameterized \(d\)-scattered set ⋮ Nonrepetitive colorings of graphs ⋮ Empirical Evaluation of Approximation Algorithms for Generalized Graph Coloring and Uniform Quasi-wideness ⋮ Algorithmic Applications of Tree-Cut Width ⋮ Unnamed Item ⋮ Improved Bounds for the Excluded-Minor Approximation of Treedepth ⋮ On Digraph Width Measures in Parameterized Algorithmics ⋮ Complexity of planar signed graph homomorphisms to cycles ⋮ A surprising permanence of old motivations (a not-so-rigid story) ⋮ Colouring graphs with bounded generalized colouring number ⋮ On the complexity of \(H\)-colouring planar graphs ⋮ Homomorphisms of triangle-free graphs without a \(K_{5}\)-minor ⋮ Unnamed Item ⋮ Colored cut games ⋮ Obstructions for Tree-depth ⋮ Counting Homomorphisms to Sparse Graphs ⋮ From \(\chi\)- to \(\chi_p\)-bounded classes ⋮ Unnamed Item ⋮ The Grad of a Graph and Classes with Bounded Expansion ⋮ Colourings of the Cartesian Product of Graphs and Multiplicative Sidon Sets ⋮ Fraternal Augmentations of graphs, Coloration and Minors ⋮ On Treewidth and Related Parameters of Random Geometric Graphs ⋮ Graphs of bounded depth‐2 rank‐brittleness ⋮ A \(p\)-centered coloring for the grid using \(O(p)\) colors ⋮ Arboreal categories and equi-resource homomorphism preservation theorems ⋮ Arboreal Categories: An Axiomatic Theory of Resources ⋮ SAT backdoors: depth beats size ⋮ CSP beyond tractable constraint languages ⋮ Edge and pair queries-random graphs and complexity ⋮ Hamiltonian Cycle Parameterized by Treedepth in Single Exponential Time and Polynomial Space ⋮ Efficient interprocedural data-flow analysis using treedepth and treewidth ⋮ The PACE 2020 Parameterized Algorithms and Computational Experiments Challenge: Treedepth.

Cites Work