On the Band-, Tree-, and Clique-Width of Graphs with Bounded Vertex Degree

DOI10.1137/S0895480102419755zbMath1081.05098MaRDI QIDQ4652630

Dieter Rautenbach, Vadim V. Lozin

Publication date: 28 February 2005

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

zbMATH Keywords

bandwidthdegreetree-width

Mathematics Subject Classification ID

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

Related Items (38)

Tree-width dichotomy ⋮ Vertex coloring of graphs with few obstructions ⋮ Colouring diamond-free graphs ⋮ Characterizations of \((4 K_1,C_4,C_5)\)-free graphs ⋮ Graph isomorphism for \((H_1, H_2)\)-free graphs: an almost complete dichotomy ⋮ Colouring square-free graphs without long induced paths. ⋮ Bounding the Clique-Width of H-free Chordal Graphs ⋮ Clique-Width of Graph Classes Defined by Two Forbidden Induced Subgraphs ⋮ Colouring of graphs with Ramsey-type forbidden subgraphs ⋮ Bounding the mim‐width of hereditary graph classes ⋮ Clique‐width: Harnessing the power of atoms ⋮ Bounding clique-width via perfect graphs ⋮ Tree-Width and Optimization in Bounded Degree Graphs ⋮ Clique-Width for Graph Classes Closed under Complementation ⋮ Boundary Classes of Planar Graphs ⋮ Classifying the clique-width of \(H\)-free bipartite graphs ⋮ Induced minor free graphs: isomorphism and clique-width ⋮ Minimal classes of graphs of unbounded clique-width ⋮ Computing the Clique-Width of Large Path Powers in Linear Time via a New Characterisation of Clique-Width ⋮ NP-hard graph problems and boundary classes of graphs ⋮ Critical hereditary graph classes: a survey ⋮ The behavior of clique-width under graph operations and graph transformations ⋮ Bounding the Mim-Width of Hereditary Graph Classes. ⋮ Coloring vertices of claw-free graphs in three colors ⋮ Recent developments on graphs of bounded clique-width ⋮ On the complexity of the dominating induced matching problem in hereditary classes of graphs ⋮ Colouring Vertices of Triangle-Free Graphs ⋮ Upper domination: towards a dichotomy through boundary properties ⋮ Clique-width and well-quasi-ordering of triangle-free graph classes ⋮ Bounding Clique-Width via Perfect Graphs ⋮ Bounding the clique-width of \(H\)-free split graphs ⋮ Unnamed Item ⋮ The intersection of two vertex coloring problems ⋮ A Boundary Property for Upper Domination ⋮ On structural parameterizations of firefighting ⋮ Coloring Graphs with Constraints on Connectivity ⋮ Colouring vertices of triangle-free graphs without forests ⋮ On the maximum independent set problem in graphs of bounded maximum degree

This page was built for publication: On the Band-, Tree-, and Clique-Width of Graphs with Bounded Vertex Degree