Cutwidth of Split Graphs and Threshold Graphs

DOI10.1137/080741197zbMath1237.05089OpenAlexW2018228760MaRDI QIDQ3225130

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 graphscutwidththreshold graphsbisection width

Mathematics Subject Classification ID

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

Related Items (7)

On the kernelization of split graph problems ⋮ Strong SDP based bounds on the cutwidth of a graph ⋮ Cutwidth: obstructions and algorithmic aspects ⋮ The structure of graphs not admitting a fixed immersion ⋮ On cutwidth parameterized by vertex cover ⋮ Kernelization of Two Path Searching Problems on Split Graphs ⋮ Vertex deletion on split graphs: beyond 4-hitting set

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