Grad and classes with bounded expansion. I: Decompositions

DOI10.1016/j.ejc.2006.07.013zbMath1156.05056arXivmath/0508323MaRDI QIDQ2426456

Patrice Ossona de Mendez, Jaroslav Nešetřil

Publication date: 22 April 2008

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

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

Mathematics Subject Classification ID

05C75: Structural characterization of families of graphs

05C83: Graph minors

Related Items

On forbidden subdivision characterizations of graph classes, Colouring games on outerplanar graphs and trees, Fraternal augmentations, arrangeability and linear Ramsey numbers, Generalization of transitive fraternal augmentations for directed graphs and its applications, A surprising permanence of old motivations (a not-so-rigid story), Grad and classes with bounded expansion. II: Algorithmic aspects, Grad and classes with bounded expansion. III: Restricted graph homomorphism dualities, Tree-Width and Optimization in Bounded Degree Graphs

Uses Software

• PIGALE

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Graph minors. I. Excluding a forest
• An algorithm for fraternal orientation of graphs
• S-functions for graphs
• On acyclic colorings of planar graphs
• Homomorphisms of edge-colored graphs and Coxeter groups
• Graph minors. XVI: Excluding a non-planar graph
• Optimal node ranking of tree in linear time
• Excluding any graph as a minor allows a low tree-width 2-coloring
• The extremal function for complete minors
• Coloring with no 2-colored \(P_4\)'s
• On acyclic colorings of graphs on surfaces
• Grad and classes with bounded expansion. II: Algorithmic aspects
• Tree-depth, subgraph coloring and homomorphism bounds
• Homomorphiesätze für Graphen
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Linear time low tree-width partitions and algorithmic consequences
• An extremal function for contractions of graphs
• The Grad of a Graph and Classes with Bounded Expansion
• Fraternal Augmentations of graphs, Coloration and Minors
• A relationship between triangulated graphs, comparability graphs, proper interval graphs, proper circular-arc graphs, and nested interval graphs
• Acyclic colorings of planar graphs