Characterizing graphs of small carving-width

DOI10.1016/j.dam.2013.02.036zbMath1286.05036OpenAlexW2007761372MaRDI 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

immersionobstruction setcarving-width

Mathematics Subject Classification ID

Trees (05C05) Distance in graphs (05C12) Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

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

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