Clique-width for hereditary graph classes
From MaRDI portal
Publication:5149166
DOI10.1017/9781108649094.002zbMath1476.05175arXiv1901.00335OpenAlexW2963678182MaRDI QIDQ5149166
Konrad K. Dabrowski, Daniël Paulusma, Matthew Johnson
Publication date: 6 February 2021
Published in: Surveys in Combinatorics 2019 (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1901.00335
graph colouringinduced subgraphclique-widthgraph isomorphismhereditary graph classgraph containment relationwidth parameterwell-quasi-orderability
Structural characterization of families of graphs (05C75) Coloring of graphs and hypergraphs (05C15)
Related Items
Uncountably many minimal hereditary classes of graphs of unbounded clique-width, Solving problems on generalized convex graphs via mim-width, Partitioning \(H\)-free graphs of bounded diameter, Polynomially bounding the number of minimal separators in graphs: reductions, sufficient conditions, and a dichotomy theorem, Minimal classes of graphs of unbounded clique-width defined by finitely many forbidden induced subgraphs, Graph isomorphism for \((H_1, H_2)\)-free graphs: an almost complete dichotomy, Steiner trees for hereditary graph classes: a treewidth perspective, Finding matching cuts in \(H\)-free graphs, Bounding the mim‐width of hereditary graph classes, Clique‐width: Harnessing the power of atoms, A class of graphs with large rankwidth, (Theta, triangle)‐free and (even hole, K4)‐free graphs. Part 2: Bounds on treewidth, Treewidth versus clique number. II: Tree-independence number, On algorithmic applications of sim-width and mim-width of \((H_1,H_2)\)-free graphs, List \(k\)-colouring \(P_t\)-free graphs: a mim-width perspective, Solving problems on generalized convex graphs via mim-width, Contracting to a longest path in H-free graphs, Bounding the Mim-Width of Hereditary Graph Classes., The Weisfeiler-Leman dimension of chordal bipartite graphs without bipartite claw, Treewidth versus Clique Number. I. Graph Classes with a Forbidden Structure, Faster 3-Coloring of Small-Diameter Graphs, Tree Pivot-Minors and Linear Rank-Width
