Graph Classes: A Survey
From MaRDI portal
Publication:4243764
DOI10.1137/1.9780898719796zbMath0919.05001OpenAlexW1579049696MaRDI QIDQ4243764
Van Bang Le, Andreas Brandstädt, Jeremy P. Spinrad
Publication date: 24 May 1999
Full work available at URL: https://doi.org/10.1137/1.9780898719796
Research exposition (monographs, survey articles) pertaining to combinatorics (05-02) Structural characterization of families of graphs (05C75) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (05Cxx)
Related Items
Clique-width of path powers, Enumerating minimal connected dominating sets in graphs of bounded chordality, Win-win kernelization for degree sequence completion problems, Weighted independent sets in classes of \(P_6\)-free graphs, Clique cycle-transversals in distance-hereditary graphs, Circular convex bipartite graphs: feedback vertex sets, A unified approach to recognize squares of split graphs, On the OBDD representation of some graph classes, On containment graphs of paths in a tree, A Gröbner basis characterization for chordal comparability graphs, Induced subgraphs of graphs with large chromatic number. I. Odd holes, Star chromatic bounds, Complexity of domination, Hamiltonicity and treewidth for tree convex bipartite graphs, Largest chordal and interval subgraphs faster than \(2^n\), Structure of squares and efficient domination in graph classes, A note on path domination, Threshold-coloring and unit-cube contact representation of planar graphs, Characterizing width two for variants of treewidth, On equistable, split, CIS, and related classes of graphs, Ferrers dimension of grid intersection graphs, New results on word-representable graphs, A new LBFS-based algorithm for cocomparability graph recognition, Minimal dominating sets in interval graphs and trees, On neighborhood-Helly graphs, Thin strip graphs, Maximum weight independent sets in classes related to claw-free graphs, Characterization and recognition of some opposition and coalition graph classes, A sufficient condition to extend polynomial results for the maximum independent set problem, The minimum vulnerability problem on specific graph classes, Graph modification problem for some classes of graphs, Series parallel digraphs with loops, On the rainbow connectivity of graphs: complexity and FPT algorithms, Color-bounded hypergraphs. VI: Structural and functional jumps in complexity, Satisfiability of acyclic and almost acyclic CNF formulas, A note on sparseness conditions on chordless vertices of cycles, On atomic structure of \(P_5\)-free subclasses and maximum weight independent set problem, Preprocessing subgraph and minor problems: when does a small vertex cover help?, Minimal dominating sets in graph classes: combinatorial bounds and enumeration, Graphs whose adjacency matrices have rank equal to the number of distinct nonzero rows, Two characterisations of the minimal triangulations of permutation graphs, Parameterized complexity of vertex deletion into perfect graph classes, Feedback vertex sets on restricted bipartite graphs, Data reduction for graph coloring problems, Fixed-parameter algorithms for cochromatic number and disjoint rectangle stabbing via iterative localization, Split clique graph complexity, Fast exact algorithm for \(L(2,1)\)-labeling of graphs, (Nearly-)tight bounds on the contiguity and linearity of cographs, The cluster deletion problem for cographs, Graph classes and Ramsey numbers, A characterization of line graphs that are squares of graphs, Finding clubs in graph classes, Permutation bigraphs and interval containments, A characterization of substar graphs, Complexity of finding maximum regular induced subgraphs with prescribed degree, Vertex-decomposable graphs, codismantlability, Cohen-Macaulayness, and Castelnuovo-Mumford regularity, Organizing the atoms of the clique separator decomposition into an atom tree, Finding intersection models: from chordal to Helly circular-arc graphs, On the spectrum of threshold graphs, Weighted maximum-clique transversal sets of graphs, Clique separator decomposition of hole-free and diamond-free graphs and algorithmic consequences, On weighted efficient total domination, Random generation and enumeration of bipartite permutation graphs, Split decomposition and graph-labelled trees: characterizations and fully dynamic algorithms for totally decomposable graphs, Edge search number of cographs, Locally identifying colourings for graphs with given maximum degree, Edge contractions in subclasses of chordal graphs, A note on connected dominating sets of distance-hereditary graphs, Four-cycled graphs with topological applications, Bandwidth of convex bipartite graphs and related graphs, The recognition of triangle graphs, A fully dynamic algorithm for the recognition of \(P_4\)-sparse graphs, Restricted vertex multicut on permutation graphs, Computing role assignments of proper interval graphs in polynomial time, Efficient total domination in digraphs, Subgraph isomorphism in graph classes, A survey of the algorithmic aspects of modular decomposition, Characterizing paths graphs on bounded degree trees by minimal forbidden induced subgraphs, An approximation algorithm for the tree \(t\)-spanner problem on unweighted graphs via generalized chordal graphs, Induced subgraph isomorphism on proper interval and bipartite permutation graphs, On the number of minimal dominating sets on some graph classes, Polynomial-time algorithms for weighted efficient domination problems in AT-free graphs and dually chordal graphs, Characterizing and computing the structure of clique intersections in strongly chordal graphs, Complete monotonicity for inverse powers of some combinatorially defined polynomials, On graphs associated to sets of rankings, Maximum weight independent sets in odd-hole-free graphs without dart or without bull, The Dilworth number of auto-chordal bipartite graphs, Polynomial time recognition of squares of Ptolemaic graphs and 3-sun-free split graphs, Spanning trees with nonseparating paths, Comparing the metric and strong dimensions of graphs, Identification, location-domination and metric dimension on interval and permutation graphs. I: Bounds., Broadcasting on cactus graphs, The complexity of dominating set reconfiguration, The behavior of clique-width under graph operations and graph transformations, End-vertices of LBFS of (AT-free) bigraphs, On graphs without a \(C_{4}\) or a diamond, Helly theorems for 3-Steiner and 3-monophonic convexity in graphs, Block-graph width, Bounding \(\chi \) in terms of \(\omega \) and \(\varDelta \) for some classes of graphs, Witness (Delaunay) graphs, Spanning trees in random series-parallel graphs, Characterizations for co-graphs defined by restricted NLC-width or clique-width operations, Minimal separators in \(P_4\)-sparse graphs, The micro-world of cographs, Solving problems on generalized convex graphs via mim-width, Cyclability in graph classes, A decentralized control mechanism for stream processing networks, Structure and linear time recognition of 3-leaf powers, Complexity aspects of generalized Helly hypergraphs, On the structure of certain intersection graphs, On independent vertex sets in subclasses of apple-free graphs, \(\lambda\)-coloring matrogenic graphs, Strictly chordal graphs are leaf powers, The interval-merging problem, Toughness and Hamiltonicity in \(k\)-trees, All minimal prime extensions of hereditary classes of graphs, Algorithmic uses of the Feferman-Vaught theorem, The Brown-Colbourn conjecture on zeros of reliability polynomials is false, Networks with small stretch number, Cover-incomparability graphs and chordal graphs, Maximal proper subgraphs of median graphs, Time slot scheduling of compatible jobs, Partially ordered knapsack and applications to scheduling, Characterization of \(P_{6}\)-free graphs, Efficient algorithms for the minimum connected domination on trapezoid graphs, Topological mappings between graphs, trees and generalized trees, A new characterization of unichord-free graphs, Interval scheduling and colorful independent sets, Dependence polynomials of some graph operations, Graph limits and hereditary properties, Graph classes with and without powers of bounded clique-width, Enumerating minimal dominating sets in chordal bipartite graphs, Polynomial-time algorithms for subgraph isomorphism in small graph classes of perfect graphs, On the intersection of tolerance and cocomparability graphs, Games on interval and permutation graph representations, The firefighter problem on graph classes, Farey graphs as models for complex networks, On the Colin de Verdière number of graphs, Computing minimum distortion embeddings into a path for bipartite permutation graphs and threshold graphs, Graph coloring with rejection, Graph operations on parity games and polynomial-time algorithms, Algorithmic aspects of switch cographs, Weighted independent sets in a subclass of \(P_6\)-free graphs, The chromatic number of a signed graph, Weighted efficient domination in two subclasses of \(P_6\)-free graphs, Almost every graph is divergent under the biclique operator, On orthogonal ray trees, Partial characterizations of circle graphs, Acyclic and star colorings of cographs, \(L(2,1)\)-labeling of perfect elimination bipartite graphs, A characterization of chain probe graphs, Two characterizations of chain partitioned probe graphs, Stability preserving transformations of graphs, Bandwidth on AT-free graphs, How to guard a graph?, A characterization of claw-free \(b\)-perfect graphs, Separable \(d\)-permutations and guillotine partitions, Chordal bipartite graphs with high boxicity, A simple linear-time recognition algorithm for weakly quasi-threshold graphs, Path-bicolorable graphs, Counting the number of independent sets in chordal graphs, Approximability results for the maximum and minimum maximal induced matching problems, Polynomial cases for the vertex coloring problem, Space-efficient biconnected components and recognition of outerplanar graphs, Variations of \(Y\)-dominating functions on graphs, Geodetic and Steiner geodetic sets in 3-Steiner distance hereditary graphs, On the complexity of generalized chromatic polynomials, Extremal perfect graphs for a bound on the domination number, The 0-1 inverse maximum stable set problem, Improved algorithms and complexity results for power domination in graphs, Linear-time algorithm for the paired-domination problem in convex bipartite graphs, Minimum entropy combinatorial optimization problems, Treewidth computations. I: Upper bounds, Some remarks on the geodetic number of a graph, Rooted directed path graphs are leaf powers, On the complexity of recognizing directed path families, Altitude of wheels and wheel-like graphs, Enumeration of the perfect sequences of a chordal graph, Edge critical cops and robber, Mixed unit interval graphs, Multiflows in symmetric digraphs, An \(O(nm)\)-time certifying algorithm for recognizing HHD-free graphs, On distance-3 matchings and induced matchings, On the complexity of the dominating induced matching problem in hereditary classes of graphs, Graphs of linear clique-width at most 3, On the complete width and edge clique cover problems, On tree representations of relations and graphs: symbolic ultrametrics and cograph edge decompositions, The induced separation dimension of a graph, Enumerating some stable partitions involving Stirling and \(r\)-Stirling numbers of the second kind, Some variations of perfect graphs, On the computational complexity of vertex integrity and component order connectivity, Nonempty intersection of longest paths in series-parallel graphs, Edge-coloring of 3-uniform hypergraphs, Enumerating minimal dominating sets in chordal graphs, The price of connectivity for cycle transversals, Recognizing vertex intersection graphs of paths on bounded degree trees, Generalized rainbow connectivity of graphs, Maximum weight independent sets in hole- and co-chair-free graphs, Improved approximability and non-approximability results for graph diameter decreasing problems, Containment relations in split graphs, On algorithms for (\(P_5\), gem)-free graphs, Perfect edge domination and efficient edge domination in graphs, Triangle-free graphs and forbidden subgraphs, On claw-free asteroidal triple-free graphs, Weighted efficient domination problem on some perfect graphs, Cops and robbers on intersection graphs, Computing a clique tree with the algorithm maximal label search, Strict chordal digraphs viewed as graphs with distinguished edges, The number of spanning trees of an infinite family of outerplanar, small-world and self-similar graphs, On maximum common subgraph problems in series-parallel graphs, Enumeration and maximum number of minimal connected vertex covers in graphs, The \(k\)-hop connected dominating set problem: approximation and hardness, On the dominating induced matching problem: spectral results and sharp bounds, Combinatorial problems on \(H\)-graphs, Polynomial time algorithms for variants of graph matching on partial \(k\)-trees, Efficient minus and signed domination in graphs, On the \(k\)-path partition of graphs., On universally easy classes for NP-complete problems., On linear and circular structure of (claw, net)-free graphs, On variations of \(P_{4}\)-sparse graphs, Subgraph trees in graph theory, Stability number of bull- and chair-free graphs revisited, The complexity of the locally connected spanning tree problem, Maximum independent set and maximum clique algorithms for overlap graphs, An approach to solving \(A^{k}=J-I\), On the structure and stability number of \(P_{5}\)- and co-chair-free graphs, Induced matchings in asteroidal triple-free graphs, Distance labeling scheme and split decomposition, Algorithms for graphs with small octopus, A linear algorithm for the Hamiltonian completion number of the line graph of a cactus., A fully dynamic algorithm for modular decomposition and recognition of cographs., (\(P_{5}\), diamond)-free graphs revisited: Structure and linear time optimization., On simplicial and co-simplicial vertices in graphs., Recognizing quasi-triangulated graphs., Decomposing complete edge-chromatic graphs and hypergraphs. Revisited, Certifying algorithms for recognizing proper circular-arc graphs and unit circular-arc graphs, On the complexity of some subgraph problems, Characterising \((k,\ell )\)-leaf powers, Series-parallel chromatic hypergraphs, Dimension-2 poset competition numbers and dimension-2 poset double competition numbers, Absolute retracts and varieties generated by chordal graphs, A new characterization of \(P_{6}\)-free graphs, Characterizing and computing minimal cograph completions, The Steiner forest problem revisited, Exact leaf powers, The clique operator on circular-arc graphs, Structural similarity of directed universal hierarchical graphs: a low computational complexity approach, On the complexity of signed and minus total domination in graphs, Hardness and approximation of minimum distortion embeddings, On the complexity of the sandwich problems for strongly chordal graphs and chordal bipartite graphs, NP-completeness results for some problems on subclasses of bipartite and chordal graphs, The induced matching and chain subgraph cover problems for convex bipartite graphs, On compact and efficient routing in certain graph classes, On a cycle partition problem, The stable set polytope for some extensions of \(P_4\)-free graphs, A clique-difference encoding scheme for labelled \(k\)-path graphs, Closest 4-leaf power is fixed-parameter tractable, Efficient algorithms for Roman domination on some classes of graphs, Mutual exclusion scheduling with interval graphs or related classes. I, Disjoint paths in symmetric digraphs, An improved algorithm for the longest induced path problem on \(k\)-chordal graphs, On the inapproximability of independent domination in \(2P_3\)-free perfect graphs, Structure and stability number of chair-, co-P- and gem-free graphs revisited, Cover-incomparability graphs of posets, Laplacian spectrum of weakly quasi-threshold graphs, Universal augmentation schemes for network navigability, The complexity of clique graph recognition, Two minimal forbidden subgraphs for double competition graphs of posets of dimension at most two, Cage-amalgamation graphs, a common generalization of chordal and median graphs, On a property of minimal triangulations, Cubicity of threshold graphs, Finding Hamiltonian cycles in \(\{\)quasi-claw, \(K_{1,5},K_{1,5} + e\}\)-free graphs with bounded Dilworth numbers, Localized and compact data-structure for comparability graphs, Partial characterizations of clique-perfect graphs II: Diamond-free and Helly circular-arc graphs, The graph sandwich problem for \(P_4\)-sparse graphs, On star and caterpillar arboricity, Cube intersection concepts in median graphs, A witness version of the cops and robber game, Algorithmic aspects of a general modular decomposition theory, Dynamically maintaining split graphs, Labeling bipartite permutation graphs with a condition at distance two, Treelike comparability graphs, The clique-separator graph for chordal graphs, Integration of topological measures for eliminating non-specific interactions in protein interaction networks, Laminar structure of ptolemaic graphs with applications, The NLC-width and clique-width for powers of graphs of bounded tree-width, Some optimization problems on weak-bisplit graphs, Efficient robust algorithms for the maximum weight stable set problem in chair-free graph classes, Simplicial powers of graphs, A forbidden induced subgraph characterization of distance-hereditary 5-leaf powers, Tree-length equals branch-length, Ordered interval routing schemes, Bandwidth of bipartite permutation graphs in polynomial time, Characterizations and recognition of circular-arc graphs and subclasses: a survey, Brambles and independent packings in chordal graphs, Steiner intervals, geodesic intervals, and betweenness, On 3-Steiner simplicial orderings, Partitioning graphs into complete and empty graphs, On stable cutsets in graphs, Parallel and serial hypercoherences, Partition-distance: A problem and class of perfect graphs arising in clustering, Tree spanners on chordal graphs: complexity and algorithms, Biclique comparability digraphs of bipartite graphs and minimum ranks of partial matrices, Chordal probe graphs, On the convexity number of graphs, Finding a sun in building-free graphs, Requiring that minimal separators induce complete multipartite subgraphs, Maximum weight independent sets for (\(P_7\),triangle)-free graphs in polynomial time, Route-enabling graph orientation problems, The longest path problem is polynomial on cocomparability graphs, Eccentric counts, connectivity and chordality, The complexity of connected dominating sets and total dominating sets with specified induced subgraphs, On computing a minimum secure dominating set in block graphs, Computational aspects of greedy partitioning of graphs, Integral mixed unit interval graphs, On the (non-)existence of polynomial kernels for \(P _{l }\)-free edge modification problems, Proper interval vertex deletion, Interval graph limits, Colouring of \((P_3 \cup P_2)\)-free graphs, Star coloring of certain graph classes, Total coloring of rooted path graphs, Graphs vertex-partitionable into strong cliques, Stable sets in \(\{\mathrm{ISK4,wheel}\}\)-free graphs, Output-polynomial enumeration on graphs of bounded (local) linear MIM-width, Fully dynamic representations of interval graphs, A fully dynamic graph algorithm for recognizing interval graphs, The 1-fixed-endpoint path cover problem is Polynomial on interval graphs, Counting minimal transversals of \(\beta\)-acyclic hypergraphs, A min-max property of chordal bipartite graphs with applications, Strongly unichord-free graphs, Counting independent sets in cocomparability graphs, Deciding whether there are infinitely many prime graphs with forbidden induced subgraphs, Polynomial \(\chi \)-binding functions and forbidden induced subgraphs: a survey, Tractabilities and intractabilities on geometric intersection graphs, Classifying \(k\)-edge colouring for \(H\)-free graphs, List matrix partitions of graphs representing geometric configurations, Maximum induced matching algorithms via vertex ordering characterizations, Cost and accuracy aware scientific workflow retrieval based on distance measure, Convex and isometric domination of (weak) dominating pair graphs, Progress on the description of identifying code polyhedra for some families of split graphs, Element distinctness revisited, Recent results on containment graphs of paths in a tree, Complexity of some graph-based bounds on the probability of a union of events, A counterexample regarding labelled well-quasi-ordering, Distribution of global defensive \(k\)-alliances over some graph products, On upper total domination versus upper domination in graphs, Finding maximum edge bicliques in convex bipartite graphs, Distance-hereditary comparability graphs, The P versus NP-complete dichotomy of some challenging problems in graph theory, Towards a comprehensive theory of conflict-tolerance graphs, Measuring instance difficulty for combinatorial optimization problems, Efficient algorithms for the double traveling salesman problem with multiple stacks, Local temporal logic is expressively complete for cograph dependence alphabets, Recognition and computation of minimal triangulations for AT-free claw-free and co-comparability graphs, Tree decompositions with small cost, On the structure of (\(P_{5}\),\,gem)-free graphs, Linear-time modular decomposition of directed graphs, Chordal co-gem-free and (\(P_{5}\),\,gem)-free graphs have bounded clique-width, Strong branchwidth and local transversals, Graph isomorphism completeness for chordal bipartite graphs and strongly chordal graphs, On the generation of circuits and minimal forbidden sets, The mathematics of xenology: di-cographs, symbolic ultrametrics, 2-structures and tree-representable systems of binary relations, Decision and approximation complexity for identifying codes and locating-dominating sets in restricted graph classes, Covering planar graphs with forests, Searching for square-complementary graphs: complexity of recognition and further nonexistence results, Generalized subgraph-restricted matchings in graphs, Chromatic bounds for some classes of \(2 K_2\)-free graphs, Contraction and deletion blockers for perfect graphs and \(H\)-free graphs, An exact cutting plane algorithm to solve the selective graph coloring problem in perfect graphs, Efficient domination for classes of \(P_6\)-free graphs, Independent sets and hitting sets of bicolored rectangular families, On \(k\)-tree containment graphs of paths in a tree, Cluster deletion on interval graphs and split related graphs, Subexponential parameterized algorithms and kernelization on almost chordal graphs, Forbidden subgraphs of power graphs, Representing graphs as the intersection of cographs and threshold graphs, A vertex ordering characterization of simple-triangle graphs, Maximum weight independent sets for (\(S_{1,2,4}\),triangle)-free graphs in polynomial time, A fast shortest path algorithm on terrain-like graphs, On the threshold of intractability, Finding a maximum induced matching in weakly chordal graphs, Independent sets in \((P_4+P_4\),triangle)-free graphs, Ambush cops and robbers, On the domination search number, Bipartite-perfect graphs, Recognition of some perfectly orderable graph classes, On list \(k\)-coloring convex bipartite graphs, Avoidable vertices and edges in graphs: existence, characterization, and applications, \(\mathcal{U}\)-bubble model for mixed unit interval graphs and its applications: the MaxCut problem revisited, (\(k,+\))-distance-hereditary graphs, The \(\text{v} \)-number of monomial ideals, A type of algebraic structure related to sets of intervals, A polynomial kernel for bipartite permutation vertex deletion, Distributed interactive proofs for the recognition of some geometric intersection graph classes, Minimum feedback vertex set and acyclic coloring., Maximum Weight Stable Set on graphs without claw and co-claw (and similar graph classes) can be solved in linear time., Approximating minimum cocolorings., The threshold dimension and irreducible graphs, Hyperbolic bridged graphs, Intersection graphs of maximal hypercubes, Linear algorithms for red and blue domination in convex bipartite graphs, Length-bounded cuts: proper interval graphs and structural parameters, Preprocessing vertex-deletion problems: characterizing graph properties by low-rank adjacencies, Parallel edges in ribbon graphs and interpolating behavior of partial-duality polynomials, The complexity of approximating the complex-valued Potts model, Characterizing atoms that result from decomposition by clique separators, The spectral determinations of connected multicone graphs \(K_{\mathcal{W}} \operatorname{\nabla} mCP(n)\), A new approach on locally checkable problems, On the iterated edge-biclique operator, Characterizing and computing weight-equitable partitions of graphs, An \(O( n^{3})\)-time recognition algorithm for hhds-free graphs, How to use spanning trees to navigate in graphs, Forced pairs in \(A\)-Stick graphs, Well-partitioned chordal graphs, Faster recognition of clique-Helly and hereditary clique-Helly graphs, Linear structure of bipartite permutation graphs and the longest path problem, Subtree filament graphs are subtree overlap graphs, Polynomial algorithms for protein similarity search for restricted mRNA structures, Note on maximal split-stable subgraphs, Injective hulls of various graph classes, A general framework for path convexities, Double-threshold permutation graphs, New results on independent sets in extensions of \(2K_2\)-free graphs, Partitioning \(H\)-free graphs of bounded diameter, An adjacency labeling scheme based on a decomposition of trees into caterpillars, From modular decomposition trees to level-1 networks: pseudo-cographs, polar-cats and prime polar-cats, The existence of a pure Nash equilibrium in the two-player competitive diffusion game on graphs having chordality, Recognizing simple-triangle graphs by restricted 2-chain subgraph cover, On some graph classes related to perfect graphs: a survey, Biclique graphs of interval bigraphs, A recognition algorithm for simple-triangle graphs, Parikh word representability of bipartite permutation graphs, Graph reconstruction in the congested clique, Reflexive polytopes arising from bipartite graphs with \(\gamma\)-positivity associated to interior polynomials, Maximizing the strong triadic closure in split graphs and proper interval graphs, Intersection graph of maximal stars, Structure and enumeration of \(K_4\)-minor-free links and link-diagrams, The one-cop-moves game on graphs with some special structures, The power of linear-time data reduction for maximum matching, Intersection dimension and graph invariants, Dualizing distance-hereditary graphs, Folding list of graphs obtained from a given graph, Distance eigenvalues of a cograph and their multiplicities, Reconstruction and verification of chordal graphs with a distance oracle, Integer Laplacian eigenvalues of chordal graphs, Weighted total acquisition, Fixed-treewidth-efficient algorithms for edge-deletion to interval graph classes, Homomorphisms to digraphs with large girth and oriented colorings of minimal series-parallel digraphs, Efficient enumeration of non-isomorphic distance-hereditary graphs and Ptolemaic graphs, Hybrid and generalized marked systems, On finite groups whose power graph is a cograph, Detecting fixed patterns in chordal graphs in polynomial time, On pairwise compatibility graphs having Dilworth number \(k\), Recognition of split-graphic sequences, Toll convexity, Hardness results, approximation and exact algorithms for liar's domination problem in graphs, Complexity and approximation results for the connected vertex cover problem in graphs and hypergraphs, A polynomial solution to the \(k\)-fixed-endpoint path cover problem on proper interval graphs, Pursuing a fast robber on a graph, On the minimum clique partitioning problem on weighted chordal graphs, Some completion problems for graphs without chordless cycles of prescribed lengths, On the complexity of the independent set problem in triangle graphs, Finitely forcible graphons, Equistable graphs, general partition graphs, triangle graphs, and graph products, Recognizing Helly edge-path-tree graphs and their clique graphs, The complexity of dissociation set problems in graphs, Improved bound for the dimension of posets of treewidth two, Non-inclusion and other subclasses of chordal graphs, Mim-width. II. The feedback vertex set problem, Sandwiches missing two ingredients of order four, Assortment optimization under the multinomial logit model with product synergies, The sparing number of certain graph powers, On grounded \(\llcorner\)-graphs and their relatives, Groups whose word problems are not semilinear, Cographs: eigenvalues and Dilworth number, Enumeration and maximum number of minimal dominating sets for chordal graphs, Colouring square-free graphs without long induced paths, Extremal matching energy and the largest matching root of complete multipartite graphs, Isomorphism of weighted trees and Stanley's isomorphism conjecture for caterpillars, Block-indifference graphs: characterization, structural and spectral properties, Vertex types in threshold and chain graphs, Using contracted solution graphs for solving reconfiguration problems, Eigenvalue-free interval for threshold graphs, Distance ideals of graphs, Fast algorithms for computing the characteristic polynomial of threshold and chain graphs, Mim-width. III. Graph powers and generalized distance domination problems, A note on the complexity of locating-total domination in graphs, On efficient domination for some classes of \(H\)-free bipartite graphs, Algorithm and hardness results on hop domination in graphs, On structural parameterizations for the 2-club problem, Clique-width of full bubble model graphs, Online results for black and white bin packing, Computing the metric dimension for chain graphs, Linear-time algorithms for tree root problems, Cographs which are cover-incomparability graphs of posets, Set graphs. III: Proof pearl: Claw-free graphs mirrored into transitive hereditarily finite sets, On the Galois lattice of bipartite distance hereditary graphs, Convex generalized flows, Knocking out \(P_k\)-free graphs, An effective branching strategy based on structural relationship among multiple forbidden induced subgraphs, The localization capture time of a graph, Computing the clique-separator graph for an interval graph in linear time, A survey of the all-pairs shortest paths problem and its variants in graphs, Vizing bound for the chromatic number on some graph classes, Complexity of Hamiltonian cycle reconfiguration, On the kernelization of split graph problems, On pairwise compatibility graphs having Dilworth number two, Information theoretic measures of UHG graphs with low computational complexity, Some observations on maximum weight stable sets in certain \(P_{5}\)-free graphs, The complexity of modular decomposition of Boolean functions, Boxicity and treewidth, Chordal multipartite graphs and chordal colorings, Unit ball graphs on geodesic spaces, The signature of chordal graphs and cographs, A faster diameter problem algorithm for a chordal graph, with a connection to its center problem, Characterizations of \((4 K_1,C_4,C_5)\)-free graphs, New characterizations of Gallai's \(i\)-triangulated graphs, Helly-gap of a graph and vertex eccentricities, Identification, location-domination and metric dimension on interval and permutation graphs. II: Algorithms and complexity, Extending partial representations of interval graphs, New graph classes characterized by weak vertex separators and two-pairs, An efficient algorithm for counting Markov equivalent DAGs, Mutual visibility in graphs, Biclique graph of bipartite permutation graphs, The lexicographic product of some chordal graphs and of cographs preserves \(b\)-continuity, On polygon numbers of circle graphs and distance hereditary graphs, 1-perfectly orientable \(K_4\)-minor-free and outerplanar graphs, FPT algorithms to compute the elimination distance to bipartite graphs and more, Completion to chordal distance-hereditary graphs: a quartic vertex-kernel, Complete edge-colored permutation graphs, Drawing outerplanar graphs using thirteen edge lengths, Uniform clutters and dominating sets of graphs, When an optimal dominating set with given constraints exists, Weighted and locally bounded list-colorings in split graphs, cographs, and partial \(k\)-trees, Steiner distance and convexity in graphs, Chordal bipartite completion of colored graphs, Counting hexagonal patches and independent sets in circle graphs, Variations of maximum-clique transversal sets on graphs, A polynomial algorithm for some preemptive multiprocessor task scheduling problems, On the complexity of recognizing Stick, BipHook and max point-tolerance graphs, Classes of perfect graphs, Routing equal-size messages on a slotted ring, Distance-\(d\) independent set problems for bipartite and chordal graphs, Approximation algorithms for node deletion problems on bipartite graphs with finite forbidden subgraph characterization, Reconfiguration of cliques in a graph, Fair allocation of indivisible items with conflict graphs, On opposition graphs, coalition graphs, and bipartite permutation graphs, Approximating the path-distance-width for AT-free graphs and graphs in related classes, Computing a minimum outer-connected dominating set for the class of chordal graphs, Computing square roots of trivially perfect and threshold graphs, \([1,2\)-sets in graphs], Integrally normalizable matrices and zero-nonzero patterns, On asteroidal sets in chordal graphs, Equistable simplicial, very well-covered, and line graphs, The maximum vertex coverage problem on bipartite graphs, Antiferromagnetic Ising model in triangulations with applications to counting perfect matchings, Graphs whose complement and square are isomorphic, Elimination schemes and lattices, Homogeneous sets and domination: A linear time algorithm for distance?hereditary graphs, On the complexity of constructing minimum changeover cost arborescences, A characterization of partial directed line graphs, Finding a minimum path cover of a distance-hereditary graph in polynomial time, The harmonious coloring problem is NP-complete for interval and permutation graphs, On the 2-rainbow domination in graphs, Decomposable graphs and definitions with no quantifier alternation, Complexity and exact algorithms for vertex multicut in interval and bounded treewidth graphs, Characterization and recognition of generalized clique-Helly graphs, Stable sets of maximum weight in (\(P_{7}\), banner)-free graphs, On clique separators, nearly chordal graphs, and the Maximum Weight Stable Set Problem, Equistable distance-hereditary graphs, Simple permutations: Decidability and unavoidable substructures, Mutual exclusion scheduling with interval graphs or related classes. II, A matrix characterization of interval and proper interval graphs, Sources of complexity in subset choice, Subclasses of \(k\)-trees: characterization and recognition, Distance-hereditary graphs are clique-perfect, Coloring mixed hypertrees, On the interval completion of chordal graphs, Toughness in graphs -- a survey, The monadic second-order logic of graphs. XV: On a conjecture by D. Seese, Representation characterizations of chordal bipartite graphs, Improved bottleneck domination algorithms, NP-completeness results for edge modification problems, Linear layouts measuring neighbourhoods in graphs, Independent Sets in Classes Related to Chair-Free Graphs, Maxclique and unit disk characterizations of strongly chordal graphs, Characterizing and recognizing probe block graphs, Shortest Reconfiguration of Sliding Tokens on a Caterpillar, Maximum Weight Independent Sets in ( $$S_{1,1,3}$$ , bull)-free Graphs, Decomposing Cubic Graphs into Connected Subgraphs of Size Three, Reconfiguration of Steiner Trees in an Unweighted Graph, Efficient Domination for Some Subclasses of $$P_6$$ -free Graphs in Polynomial Time, Self-spanner graphs, Efficient parallel recognition of cographs, Linear-time algorithms for the Hamiltonian problems on distance-hereditary graphs, Rebuilding convex sets in graphs, Computing maximum stable sets for distance-hereditary graphs, Tandem-win graphs, A generalization of the theorem of Lekkerkerker and Boland, On the relationship between NLC-width and linear NLC-width, Independent packings in structured graphs, Minimal Dominating Sets in Graph Classes: Combinatorial Bounds and Enumeration, POLYGON DECOMPOSITION AND THE ORTHOGONAL ART GALLERY PROBLEM, Approximate L(δ1,δ2,…,δt)‐coloring of trees and interval graphs, The Complexity of Dominating Set Reconfiguration, Linear Bound in Terms of Maxmaxflow for the Chromatic Roots of Series-Parallel Graphs, VERTEX VULNERABILITY PARAMETER OF GEAR GRAPHS, RESIDUAL CLOSENESS OF WHEELS AND RELATED NETWORKS, On partitioning interval graphs into proper interval subgraphs and related problems, Characterizing directed path graphs by forbidden asteroids, When every k-cycle has at least f(k) chords, Union Closed Tree Convex Sets, BOUNDED SEARCH TREE ALGORITHMS FOR PARAMETRIZED COGRAPH DELETION: EFFICIENT BRANCHING RULES BY EXPLOITING STRUCTURES OF SPECIAL GRAPH CLASSES, Induced Separation Dimension, Vertex decomposable graphs and obstructions to shellability, How to Use Spanning Trees to Navigate in Graphs, Choosability of P 5-Free Graphs, Linear-Time Algorithms for Finding Tucker Submatrices and Lekkerkerker--Boland Subgraphs, Pairwise Compatibility Graphs: A Survey, Neighbor Isolated Tenacity of Graphs, On certain coloring parameters of Mycielski graphs of some graphs, Optimal Approximation Algorithms for Maximum Distance-Bounded Subgraph Problems, Symmetric graph-theoretic roles of two-pairs and chords of cycles, A Linear-Time Algorithm for Maximum-Cardinality Matching on Cocomparability Graphs, On Symbolic Ultrametrics, Cotree Representations, and Cograph Edge Decompositions and Partitions, Characterizing k-chordal unichord-free graphs, The Minimum Vulnerability Problem on Graphs, Erdös-Pósa Property of Obstructions to Interval Graphs, Colouring square-free graphs without long induced paths., Contact Representations of Planar Graphs: Extending a Partial Representation is Hard, Hadwiger Number of Graphs with Small Chordality, Recognizing Threshold Tolerance Graphs in $$O(n^2)$$ Time, Reconfiguration of Vertex Covers in a Graph, Deterministic Algorithms for the Independent Feedback Vertex Set Problem, Contraction Blockers for Graphs with Forbidden Induced Paths, Approximation and Kernelization for Chordal Vertex Deletion, Graphs of Linear Clique-Width at Most 3, Large Induced Subgraphs via Triangulations and CMSO, Linear-Interval Dimension and PI Orders, On cliques of Helly Circular-arc Graphs, On the complexity of variations of mixed domination on graphs†, Characterizing and Computing Minimal Cograph Completions, Mixed Search Number of Permutation Graphs, The 2-Terminal-Set Path Cover Problem and Its Polynomial Solution on Cographs, The Clique-Width of Tree-Power and Leaf-Power Graphs, Complexity and Approximation Results for the Connected Vertex Cover Problem, Characterisations and Linear-Time Recognition of Probe Cographs, Proper Helly Circular-Arc Graphs, Damaged BZip Files Are Difficult to Repair, A New Characterization of P 6-Free Graphs, Probe Ptolemaic Graphs, Minimum Distortion Embeddings into a Path of Bipartite Permutation and Threshold Graphs, A Simple Linear Time Algorithm for the Isomorphism Problem on Proper Circular-Arc Graphs, On chromatic Zagreb indices of certain graphs, Enumerating Minimal Tropical Connected Sets, Linear Clique‐Width for Hereditary Classes of Cographs, Two-Player Competitive Diffusion Game: Graph Classes and the Existence of a Nash Equilibrium, Computing Role Assignments of Proper Interval Graphs in Polynomial Time, The Effect of Various Sparsity Structures on Parallelism and Algorithms to Reveal Those Structures, Satisfiability of Acyclic and almost Acyclic CNF Formulas (II), Jump Number of Two-Directional Orthogonal Ray Graphs, Edge Contractions in Subclasses of Chordal Graphs, Unnamed Item, The Longest Path Problem is Polynomial on Cocomparability Graphs, Computing the Cutwidth of Bipartite Permutation Graphs in Linear Time, Measuring Indifference: Unit Interval Vertex Deletion, On the (Non-)existence of Polynomial Kernels for P l -free Edge Modification Problems, Proper Interval Vertex Deletion, Colinear Coloring on Graphs, Random Generation and Enumeration of Proper Interval Graphs, Then-ordered graphs: A new graph class, ON COMPUTING LONGEST PATHS IN SMALL GRAPH CLASSES, Lossy Kernels for Connected Dominating Set on Sparse Graphs, A Polynomial Time Algorithm for Longest Paths in Biconvex Graphs, SIMPLE EXTENSIONS OF COMBINATORIAL STRUCTURES, Data Reduction for Graph Coloring Problems, Parameterized Complexity of Vertex Deletion into Perfect Graph Classes, Enumeration of Minimal Dominating Sets and Variants, Complexity of approximating the oriented diameter of chordal graphs, Efficient Farthest-Point Queries in Two-terminal Series-parallel Networks, Minimum Eccentricity Shortest Paths in Some Structured Graph Classes, Exploring the Subexponential Complexity of Completion Problems, Split Clique Graph Complexity, Graph Classes with Structured Neighborhoods and Algorithmic Applications, Maximum Independent Set in 2-Direction Outersegment Graphs, Alternation Graphs, Approximability of the Path-Distance-Width for AT-free Graphs, A new representation of proper interval graphs with an application to clique-width, On some simplicial elimination schemes for chordal graphs, A Polynomial-time Algorithm for the Dominating Induced Matching Problem in the Class of Convex Graphs, On Distance-3 Matchings and Induced Matchings, Path-Bicolorable Graphs, Distance-Hereditary Comparability Graphs, The Exact Weighted Independent Set Problem in Perfect Graphs and Related Classes, Counting perfect matchings in the geometric dual, BOUNDING THE NUMBER OF REDUCED TREES, COGRAPHS, AND SERIES-PARALLEL GRAPHS BY COMPRESSION, THE COMPUTATIONAL COMPLEXITY OF AVOIDING FORBIDDEN SUBMATRICES BY ROW DELETIONS, Packing of (0, 1)-matrices, WHEN ALL MINIMAL VERTEX SEPARATORS INDUCE COMPLETE OR EDGELESS SUBGRAPHS, Circular Convex Bipartite Graphs: Feedback Vertex Set, The set of prime extensions of a graph: the finite and the infinite case, Disconnected matchings, Combining decomposition approaches for the maximum weight stable set problem, Bounds for the geometric-arithmetic index of unicyclic graphs, On stability of spanning tree degree enumerators, Enumeration of minimal tropical connected sets, Polynomial Kernel for Interval Vertex Deletion, On the edge‐biclique graph and the iterated edge‐biclique operator, Unique response Roman domination: complexity and algorithms, Leverage centrality analysis of infrastructure networks, Efficient non-isomorphic graph enumeration algorithms for subclasses of perfect graphs, Erdős–Pósa property of obstructions to interval graphs, Perfectly contractile graphs and quadratic toric rings, Deletion to scattered graph classes. II: Improved FPT algorithms for deletion to pairs of graph classes, Comparability graphs among cover-incomparability graphs, Classification of non-solvable groups whose power graph is a cograph, Injective edge-coloring of subcubic graphs, The axiomatic characterization of the interval function of distance hereditary graphs, Treewidth versus clique number. II: Tree-independence number, Global and local structure‐based influential nodes identification in wheel‐type networks, Axiomatic characterizations of Ptolemaic and chordal graphs, A survey of parameterized algorithms and the complexity of edge modification, Weighted connected matchings, Two generalizations of proper coloring: hardness and approximability, Agglomeration-Based Node Importance Analysis in Wheel-Type Networks, Certifying fully dynamic algorithms for recognition and Hamiltonicity of threshold and chain graphs, Resolving prime modules: the structure of pseudo-cographs and galled-tree explainable graphs, A characterization of unit interval bigraphs of open and closed intervals, Computing well-covered vector spaces of graphs using modular decomposition, On groups with chordal power graph, including a classification in the case of finite simple groups, Monochromatic spanning trees and matchings in ordered complete graphs, Classes of intersection digraphs with good algorithmic properties, Strong Cocomparability Graphs and Slash-Free Orderings of Matrices, Unnamed Item, Unnamed Item, Unnamed Item, Solving problems on generalized convex graphs via mim-width, Recognizing Proper Tree-Graphs, Intersection of longest paths in graph classes, On maximizing clique, clique-Helly and hereditary clique-Helly induced subgraphs, Difference graphs, On maximizing clique, clique-Helly and hereditary clique-Helly induced subgraphs, Algorithmic Aspects of Quasi-Total Roman Domination in Graphs, Counting independent sets in graphs with bounded bipartite pathwidth, Complexity classification of some edge modification problems, Graph parameters, implicit representations and factorial properties, Temporal graph classes: a view through temporal separators, On the relation of strong triadic closure and cluster deletion, Polynomial-time algorithms for the subset feedback vertex set problem on interval graphs and permutation graphs, Bandwidth and topological bandwidth of graphs with few \(P_4\)'s, Faster and enhanced inclusion-minimal cograph completion, Quasimonotone graphs, When can graph hyperbolicity be computed in linear time?, Enumeration of nonisomorphic interval graphs and nonisomorphic permutation graphs, Enumeration and maximum number of maximal irredundant sets for chordal graphs, Fully dynamic algorithm for recognition and modular decomposition of permutation graphs, Can Romeo and Juliet meet? Or rendezvous games with adversaries on graphs, Graph classes and the switch Markov chain for matchings, Constructing minimum changeover cost arborescenses in bounded treewidth graphs, Finding large degree-anonymous subgraphs is hard, On cycle transversals and their connected variants in the absence of a small linear forest, Computing subset transversals in \(H\)-free graphs, On finding separators in temporal split and permutation graphs, Incremental optimization of independent sets under the reconfiguration framework, On efficient domination for some classes of \(H\)-free chordal graphs, Recognizing \(k\)-clique extendible orderings, On finding separators in temporal split and permutation graphs, Makespan minimization on unrelated parallel machines with simple job-intersection structure and bounded job assignments, Parameterized complexity of diameter, Exact algorithms for a discrete metric labeling problem, Crossing graphs of fiber-complemented graphs, Disconnected matchings, Operations on independence numbers of certain graph classes, On the irregularity of graphs based on the arithmetic-geometric mean inequality, Destroying Bicolored $P_3$s by Deleting Few Edges, Assessing the Computational Complexity of Multi-layer Subgraph Detection, Linear-Time Generation of Random Chordal Graphs, The Micro-world of Cographs, Fair Packing of Independent Sets, A Survey on Spanning Tree Congestion, A tight relation between series-parallel graphs and bipartite distance hereditary graphs, Letter Graphs and Geometric Grid Classes of Permutations, Labelled well-quasi-order for permutation classes, Cutwidth of Split Graphs, Threshold Graphs, and Proper Interval Graphs, On δ(k)-coloring of generalized Petersen graphs, On δ(k)-coloring of powers of helm and closed helm graphs, Unnamed Item, On Weak Integer Additive Set-Indexers of Certain Graph Classes, On spectra of sentences of monadic second order logic with counting, On Edge-Length Ratios of Partial 2-Trees, Computation of Dynamic Equilibria in Series-Parallel Networks, Edge Search Number of Cographs in Linear Time, CFI Construction and Balanced Graphs, Pathwidth is NP-Hard for Weighted Trees, The Smallest Classes of Binary and Ternary Matroids Closed under Direct Sums and Complements, Unnamed Item, Unnamed Item, Unnamed Item, Graphs with sparsity order at most two: the complex case, Requiring adjacent chords in cycles, A New Class of Graphs That Satisfies the Chen‐Chvátal Conjecture, Unnamed Item, Unnamed Item, A study on the modular sumset labeling of graphs, Cograph editing: Merging modules is equivalent to editing P_4s, Bipartite Analogues of Comparability and Cocomparability Graphs, THE SPECTRAL DETERMINATIONS OF THE JOIN OF TWO FRIENDSHIP GRAPHS, Unnamed Item, Compact and localized distributed data structures, Problem Kernels for NP-Complete Edge Deletion Problems: Split and Related Graphs, GEM- AND CO-GEM-FREE GRAPHS HAVE BOUNDED CLIQUE-WIDTH, Maximum Edge Bicliques in Tree Convex Bipartite Graphs, A study on prime arithmetic integer additive set-indexers of graphs, Rainbow Vertex Coloring Bipartite Graphs and Chordal Graphs, Exploring the complexity boundary between coloring and list-coloring, The spectral characterization of the connected multicone graphs, A 3-approximation for the pathwidth of Halin graphs, The spectral determination of the connected multicone graphs, Towards Hilbert's 24th Problem: Combinatorial Proof Invariants, Star Partitions of Perfect Graphs, On the Iterated Biclique Operator, A linear‐time algorithm for the k‐fixed‐endpoint path cover problem on cographs, Crossing graphs of fiber-complemented graphs, Hardness Results and an Exact Exponential Algorithm for the Spanning Tree Congestion Problem, Ptolemaic Graphs and Interval Graphs Are Leaf Powers, Collective Additive Tree Spanners of Homogeneously Orderable Graphs, The cyclic rank completion problem with general blocks, A review on graceful and sequential integer additive set-labeled graphs, Unnamed Item, Spectral properties of cographs andP5-free graphs, Odd twists on strongly chordal graphs, Combinatorial Analysis of Growth Models for Series-Parallel Networks, Unnamed Item, The Impact of Locality in the Broadcast Congested Clique Model, Linear separation of connected dominating sets in graphs, Unnamed Item, Reconfiguration of Minimum Steiner Trees via Vertex Exchanges, Counting Perfect Matchings and the Switch Chain, Unnamed Item, Unnamed Item, Unnamed Item, Kernelization of Graph Hamiltonicity: Proper $H$-Graphs, Unnamed Item, Lossy Kernels for Connected Dominating Set on Sparse Graphs, Vertex types in some lexicographic products of graphs, Induced Embeddings into Hamming Graphs., Counting Weighted Independent Sets beyond the Permanent, The Power of Linear-Time Data Reduction for Maximum Matching, The Recognition of Simple-Triangle Graphs and of Linear-Interval Orders is Polynomial, The complexity of approximating the complex-valued Potts model, Vertex irregular reflexive labeling of disjoint union of gear and book graphs, Simplicial Powers of Graphs, Efficient Local Representations of Graphs, Chvátal’s t 0-Tough Conjecture, A Study on Topological Integer Additive Set-Labeling of Graphs, Graph Classes and Forbidden Patterns on Three Vertices, Hamiltonian Chordal Graphs are not Cycle Extendable, Unique chords of unique cycles in 3-connected planar graphs, Algorithmic aspects of k-part degree restricted domination in graphs, Graphs in which every c edges that form a tree are chords of a common cycle, OnH-antimagic decomposition of toroidal grids and triangulations, A survey on pairwise compatibility graphs, Fast and simple algorithms for counting dominating sets in distance-hereditary graphs, Fiedler vector analysis for particular cases of connected graphs, Graph complement conjecture for classes of shadow graphs, A linear time algorithm to compute a minimum restrained dominating set in proper interval graphs, Defective Coloring on Classes of Perfect Graphs, Maximum Induced Matching Algorithms via Vertex Ordering Characterizations, Linear‐Time Algorithms for Scattering Number and Hamilton‐Connectivity of Interval Graphs, What Graphs are 2-Dot Product Graphs?, Chromatic Zagreb and irregularity polynomials of graphs, On ideal sumset labelled graphs
