Characterizing graphs of small carving-width

DOI10.1016/j.dam.2013.02.036zbMath1286.05036MaRDI QIDQ2446832

Dimitrios M. Thilikos, Daniël Paulusma, Pim van 't Hof, Rémy Belmonte, Marcin Kaminski

Publication date: 22 April 2014

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2013.02.036

zbMATH Keywords

immersion; obstruction set; carving-width

Mathematics Subject Classification ID

05C05: Trees

05C12: Distance in graphs

05C78: Graph labelling (graceful graphs, bandwidth, etc.)

05C85: Graph algorithms (graph-theoretic aspects)

Related Items

Bounding branch-width, Effective computation of immersion obstructions for unions of graph classes, An analysis of the parameterized complexity of periodic timetabling

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Outerplanar obstructions for a feedback vertex set
• Forbidden graphs for tree-depth
• The structure of graphs not admitting a fixed immersion
• Graph minors XXIII. Nash-Williams' immersion conjecture
• A partial k-arboretum of graphs with bounded treewidth
• Designing multi-commodity flow trees
• Minimal acyclic forbidden minors for the family of graphs with bounded path-width
• Call routing and the ratcatcher
• Algorithms and obstructions for linear-width and related search parameters
• Forbidding Kuratowski Graphs as Immersions
• Graph Coloring and the Immersion Order
• Characterizing Graphs of Small Carving-Width
• Characterization and Recognition of Partial 3-Trees
• Graphs with Branchwidth at Most Three
• Linkless embeddings of graphs in 3-space
• Finding topological subgraphs is fixed-parameter tractable