Cutwidth of Split Graphs and Threshold Graphs

DOI10.1137/080741197zbMATH Open1237.05089OpenAlexW2018228760MaRDI QIDQ3225130FDOQ3225130

Daniel Lokshtanov, Rodica Mihai, Pinar Heggernes, Charis Papadopoulos

Publication date: 15 March 2012

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/07e8dd2ab42c6da372b416bb35c96f72affde4d7

zbMATH Keywords

split graphsthreshold graphscutwidthbisection width

Mathematics Subject Classification ID

Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Graph minors (05C83) Perfect graphs (05C17)

Cited In (10)

• Cutwidth: obstructions and algorithmic aspects
• Cut-off for large sums of graphs
• On the kernelization of split graph problems
• Strong SDP based bounds on the cutwidth of a graph
• The structure of graphs not admitting a fixed immersion
• Vertex deletion on split graphs: beyond 4-hitting set
• On cutwidth parameterized by vertex cover
• Kernelization of Two Path Searching Problems on Split Graphs
• Hypergraph Cuts with General Splitting Functions
• On the planar split thickness of graphs

This page was built for publication: Cutwidth of Split Graphs and Threshold Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3225130)