Grad and classes with bounded expansion. III: Restricted graph homomorphism dualities
From MaRDI portal
Publication:2427548
DOI10.1016/j.ejc.2007.11.019zbMath1213.05240OpenAlexW2049229625MaRDI QIDQ2427548
Jaroslav Nešetřil, Patrice Ossona de Mendez
Publication date: 13 May 2008
Published in: European Journal of Combinatorics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.ejc.2007.11.019
Related Items (40)
List rankings and on-line list rankings of graphs ⋮ Walk-powers and homomorphism bounds of planar signed graphs ⋮ Dualities and dual pairs in Heyting algebras ⋮ Hypertree-depth and minors in hypergraphs ⋮ Forbidden graphs for tree-depth ⋮ On low tree-depth decompositions ⋮ A Unified Approach to Structural Limits and Limits of Graphs with Bounded Tree-Depth ⋮ Parameterized complexity of generalized domination problems ⋮ Unnamed Item ⋮ On nowhere dense graphs ⋮ Many Facets of Dualities ⋮ Distance-two coloring of sparse graphs ⋮ Colouring, constraint satisfaction, and complexity ⋮ On forbidden subdivision characterizations of graph classes ⋮ Confronting intractability via parameters ⋮ Polynomial treedepth bounds in linear colorings ⋮ Characterisations and examples of graph classes with bounded expansion ⋮ Computing tree-depth faster than \(2^n\) ⋮ On the weak 2-coloring number of planar graphs ⋮ Homomorphism bounds and edge-colourings of \(K_{4}\)-minor-free graphs ⋮ Small graph classes and bounded expansion ⋮ First order properties on nowhere dense structures ⋮ Rank-width and tree-width of \(H\)-minor-free graphs ⋮ Computing vertex-surjective homomorphisms to partially reflexive trees ⋮ On the parameterized complexity of \([1,j\)-domination problems] ⋮ Lossy Kernels for Connected Dominating Set on Sparse Graphs ⋮ High-girth cubic graphs are homomorphic to the Clebsch graph ⋮ EXISTENCE OF MODELING LIMITS FOR SEQUENCES OF SPARSE STRUCTURES ⋮ On the Parameterized Complexity of [1,j-Domination Problems] ⋮ Empirical Evaluation of Approximation Algorithms for Generalized Graph Coloring and Uniform Quasi-wideness ⋮ Finite dualities and map-critical graphs on a fixed surface ⋮ Lossy Kernels for Connected Dominating Set on Sparse Graphs ⋮ Generalization of transitive fraternal augmentations for directed graphs and its applications ⋮ A surprising permanence of old motivations (a not-so-rigid story) ⋮ Obstructions for Tree-depth ⋮ Structural Properties of Sparse Graphs ⋮ From \(\chi\)- to \(\chi_p\)-bounded classes ⋮ Mapping Planar Graphs into Projective Cubes ⋮ Homomorphisms of Signed Graphs ⋮ Empirical Evaluation of Approximation Algorithms for Generalized Graph Coloring and Uniform Quasi-Wideness
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Tension continuous maps -- their structure and applications
- Homomorphisms and edge-colourings of planar graphs
- Universality of \(A\)-mote graphs
- On classes of relations and graphs determined by subobjects and factorobjects
- A short list color proof of Grötzsch's theorem
- Universal \(H\)-colorable graphs without a given configuration
- Universal partial order represented by means of oriented trees and other simple graphs
- Excluding any graph as a minor allows a low tree-width 2-coloring
- Duality theorems for finite structures (characterising gaps and good characterisations)
- Aspects of structural combinatorics. (Graph homomorphisms and their use)
- Grad and classes with bounded expansion. I: Decompositions
- Grad and classes with bounded expansion. II: Algorithmic aspects
- Tree-depth, subgraph coloring and homomorphism bounds
- Folding
- Cuts and bounds
- Linear time low tree-width partitions and algorithmic consequences
- Small Diameters of Duals
- Short Answers to Exponentially Long Questions: Extremal Aspects of Homomorphism Duality
This page was built for publication: Grad and classes with bounded expansion. III: Restricted graph homomorphism dualities
