The intersection graphs of subtrees in trees are exactly the chordal graphs
From MaRDI portal
Publication:2562090
DOI10.1016/0095-8956(74)90094-XzbMath0266.05101OpenAlexW1978452004WikidataQ56430108 ScholiaQ56430108MaRDI QIDQ2562090
Publication date: 1974
Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0095-8956(74)90094-x
Related Items
Minimal triangulations of graphs: a survey, A vertex incremental approach for maintaining chordality, Intersection graphs of paths in a tree, Characterizing intersection classes of graphs, Graph minors. V. Excluding a planar graph, End simplicial vertices in path graphs, Neighborhood perfect graphs, Contraction bidimensionality of geometric intersection graphs, The neighborhood polynomial of chordal graphs, Computing the union join and subset graph of acyclic hypergraphs in subquadratic time, On models of directed path graphs non rooted directed path graphs, Maximum weight independent sets and cliques in intersection graphs of filaments, On basic chordal graphs and some of its subclasses, On the algorithmic complexity of edge total domination, Hamiltonian circuits in interval graph generalizations, 10-tough chordal graphs are Hamiltonian (extended abstract), Packing and covering a tree by subtrees, A note on the colorful fractional Helly theorem, Tree-decompositions, tree-representability and chordal graphs, The maximum k-colorable subgraph problem for chordal graphs, Characterizing width two for variants of treewidth, 10-tough chordal graphs are Hamiltonian, The minimum vulnerability problem on specific graph classes, Efficient parallel algorithms for finding maximal cliques, clique trees, and minimum coloring on chordal graphs, Simplicial decompositions of graphs: A survey of applications, Algorithmic aspects of intersection graphs and representation hypergraphs, Tree representations of graphs, String graphs. I: The number of critical nonstring graphs is infinite, Two characterisations of the minimal triangulations of permutation graphs, The cluster deletion problem for cographs, On the algorithmic complexity of \(k\)-tuple total domination, Asteroidal quadruples in non rooted path graphs, A characterization of substar graphs, Algorithms for \(\mathcal{GA}\mathrm{-}\mathcal H\) reduced graphs, Finding intersection models: from chordal to Helly circular-arc graphs, Parameterized complexity and inapproximability of dominating set problem in chordal and near chordal graphs, Reduced clique graphs of chordal graphs, Split decomposition and graph-labelled trees: characterizations and fully dynamic algorithms for totally decomposable graphs, Characterization and representation problems for intersection betweennesses, Edge contractions in subclasses of chordal graphs, Almost every graph is divergent under the biclique operator, Further hardness results on rainbow and strong rainbow connectivity, Faster parameterized algorithms for \textsc{Minimum Fill-in}, 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, Representations of graphs and networks (coding, layouts and embeddings), Intersection properties of graphs, Connectivity threshold for random chordal graphs, Counting independent sets in a tolerance graph, Intersection representations of matrices by subtrees and unicycles on graphs, An inertia formula for Hermitian matrices with sparse inverses, Efficient algorithms for shortest distance queries on special classes of polygons, Complexity of rainbow vertex connectivity problems for restricted graph classes, Strict chordal and strict split digraphs, An algorithm for fraternal orientation of graphs, Representing orders by moving figures in space, Thresholds for classes of intersection graphs, The complexity of reconstructing trees from qualitative characters and subtrees, Optimization problems in multiple subtree graphs, Treewidth computations. I: Upper bounds, Separator orders in interval, cocomparability, and AT-free graphs, Computing branchwidth via efficient triangulations and blocks, Finding a maximum-weight induced \(k\)-partite subgraph of an \(i\)-triangulated graph, Dynamic programming and planarity: improved tree-decomposition based algorithms, On the complexity of computing treelength, An algorithm for testing chordality of graphs, A recognition algorithm for the intersection graphs of directed paths in directed trees, Computing role assignments of chordal graphs, Exact leaf powers, Information storage and retrieval - mathematical foundations. II: Combinatorial problems, A parallel algorithm for generating bicompatible elimination orderings of proper interval graphs, On-line approach to off-line coloring problems on graphs with geometric representations, A note on perfect Gaussian elimination, Equivalences and the complete hierarchy of intersection graphs of paths in a tree, A recognition algorithm for the intersection graphs of paths in trees, Recognizing vertex intersection graphs of paths on bounded degree trees, Graphs without large apples and the maximum weight independent set problem, Representing triangulated graphs in stars, Counting clique trees and computing perfect elimination schemes in parallel, Induced matchings, Extending cycles in graphs, All structured programs have small tree width and good register allocation, Edge-maximal graphs of branchwidth \(k\): The \(k\)-branches, An optimal algorithm for solving the searchlight guarding problem on weighted interval graphs, Intersection models of weakly chordal graphs, The clique-separator graph for chordal graphs, A partial k-arboretum of graphs with bounded treewidth, Recognizing clique graphs of directed and rooted path graphs, Brambles and independent packings in chordal graphs, The forbidden subgraph characterization of directed vertex graphs, Characterizations of strongly chordal graphs, On the representation of triangulation graphs in trees, Interval graphs and related topics, On the pathwidth of chordal graphs, Clique graphs and Helly graphs, Polynomial algorithms for the weighted perfect domination problems on chordal graphs and split graphs, Finding dominating cliques efficiently, in strongly chordal graphs and undirected path graphs, On cocolourings and cochromatic numbers of graphs, Recognition algorithm for intersection graphs of edge disjoint paths in a tree, Dominating cliques in chordal graphs, On the Algorithmic Complexity of Total Domination, The k-Domination and k-Stability Problems on Sun-Free Chordal Graphs, Disjointness graphs of segments in the space, Linear-Time Generation of Random Chordal Graphs, Sequential and parallel algorithms on compactly represented chordal and strongly chordal graphs, Characterizing directed path graphs by forbidden asteroids, Minimal elimination of planar graphs, Matrices with chordal inverse zero-patterns, Graph Minors and Parameterized Algorithm Design, What Is between Chordal and Weakly Chordal Graphs?, Approximation algorithms for maximum weight k-coverings of graphs by packings, Path Problems in Complex Networks, Unit ball graphs on geodesic spaces, Complexity and approximability of the happy set problem, Vertex Ordering Characterizations of Graphs of Bounded Asteroidal Number, An efficient algorithm for counting Markov equivalent DAGs, Intersection graphs of proper subtrees of unicyclic graphs, Bears with hats and independence polynomials, Beyond Helly graphs: the diameter problem on absolute retracts, Minimum Average Distance Clique Trees, Temporal interval cliques and independent sets, Space-efficient algorithms for reachability in directed geometric graphs, Testing isomorphism of chordal graphs of bounded leafage is fixed-parameter tractable (extended abstract), Extending partial representations of circular-arc graphs, The Neighborhood Polynomial of Chordal Graphs, Further results on Hendry's Conjecture, Two new characterizations of path graphs, Transversals of longest cycles in partial k‐trees and chordal graphs, Independent set under a change constraint from an initial solution, The diameter of AT‐free graphs, Unnamed Item, On the edge‐biclique graph and the iterated edge‐biclique operator, Clique trees of chordal graphs: leafage and 3-asteroidals, A story of diameter, radius, and (almost) Helly property, Efficient isomorphism for \(S_d\)-graphs and \(T\)-graphs, A Characterisation of the Minimal Triangulations of Permutation Graphs, Long induced paths in minor-closed graph classes and beyond, How to Use Planarity Efficiently: New Tree-Decomposition Based Algorithms, Intersecting longest paths in chordal graphs, Unnamed Item, On the structure of (pan, even hole)‐free graphs, On the complexity of recognizing Stick, BipHook and max point-tolerance graphs, Unnamed Item, A Refined Analysis of Online Path Coloring in Trees, Revisiting Decomposition by Clique Separators, Reconfiguration of cliques in a graph, Unnamed Item, Parameters Tied to Treewidth, Unnamed Item, On asteroidal sets in chordal graphs, The maximum vertex coverage problem on bipartite graphs, Characterization of classical graph classes by weighted clique graphs, An efficient representation of chordal graphs, Solving Graph Problems via Potential Maximal Cliques, Searching for better fill-in, Burning Two Worlds, 3D-interval-filament graphs, The \(k\)-edge intersection graphs of paths in a tree, Finding Temporal Paths Under Waiting Time Constraints., Tree decomposition and discrete optimization problems: a survey, On the Iterated Biclique Operator, On-line graph coloring of \({\mathbb{P}_5}\)-free graphs, The pagenumber of \(k\)-trees is \(O(k)\), Chordality of graphs associated to commutative rings, Approximation algorithms for maximum two-dimensional pattern matching, Intersection graphs of non-crossing paths, Some remarks about leaf roots, Biclique graphs and biclique matrices, Representation characterizations of chordal bipartite graphs, Maximal sub-triangulation in pre-processing phylogenetic data, Unnamed Item, Diameter determination on restricted graph families, Unnamed Item, Expansions of Chromatic Polynomials and Log-Concavity, From Path Graphs to Directed Path Graphs, Proper Interval Vertex Deletion, Connected vertex cover for \((sP_1+P_5)\)-free graphs, Minimal elimination ordering for graphs of bounded degree, The edge-orientation problem and some of its variants on weighted graphs, On \(H\)-topological intersection graphs, Two strikes against perfect phylogeny, Junction trees of general graphs, An Approximation Algorithm for the Tree t-Spanner Problem on Unweighted Graphs via Generalized Chordal Graphs, Bidimensionality and Kernels, A Polynomial Delay Algorithm for Enumerating Minimal Dominating Sets in Chordal Graphs, Characterizing path graphs by forbidden induced subgraphs, Asteroids in rooted and directed path graphs, Linear Algorithms for Chordal Graphs of Bounded Directed Vertex Leafage, On some simplicial elimination schemes for chordal graphs, Algorithms on Subtree Filament Graphs, Non-separating cliques, asteroidal number and leafage. The minimal 4-asteroidal split graphs, Contraction-Bidimensionality of Geometric Intersection Graphs, Packing of (0, 1)-matrices, Defining a Phylogenetic Tree with the Minimum Number of $r$-State Characters, Tree decompositions and social graphs, Efficient parallel algorithm to compute a doubly perfect elimination ordering of a doubly chordal graph, On the maximum number of edges in chordal graphs of bounded degree and matching number, Intersection graphs of \(k\)-acyclic families of subtrees and relational database query processing., CONNECTED LIAR'S DOMINATION IN GRAPHS: COMPLEXITY AND ALGORITHMS, Alternating cycle-free matchings, Perfect edge domination and efficient edge domination in graphs, NeST graphs, A note on independence complexes of chordal graphs and dismantling, The parallel solution of domination problems on chordal and strongly chordal graphs, Intersection graphs of concatenable subtrees of graphs, Rank inequalities for chordal graphs, A faster algorithm to recognize undirected path graphs, Families of induced trees and their intersection graphs, Tuple domination on graphs with the consecutive-zeros property, On the iterated edge-biclique operator, Tree spanners on chordal graphs: complexity and algorithms, Generating and characterizing the perfect elimination orderings of a chordal graph, An efficient parallel algorithm for the minimal elimination ordering (MEO) of an arbitrary graph, Tolerance intersection graphs of degree bounded subtrees of a tree with constant tolerance 2, Finding minimum height elimination trees for interval graphs in polynomial time, Graphs with a unique maximum independent set up to automorphisms, Regular vines with strongly chordal pattern of (conditional) independence, Clique tree generalization and new subclasses of chordal graphs, Well-partitioned chordal graphs, Isomorphism testing for \(T\)-graphs in FPT, Parameterized algorithms for Steiner tree and dominating set: bounding the leafage by the vertex leafage, Intersection graphs of vertex disjoint paths in a tree, A 2-approximation NC algorithm for connected vertex cover and tree cover, On the \(\Delta \)-interval and the \(\Delta \)-convexity numbers of graphs and graph products, Computing a clique tree with the algorithm maximal label search, Computing a minimum subset feedback vertex set on chordal graphs parameterized by leafage, Algorithmic aspects of the generalized clique-transversal problem on chordal graphs, Intersection graphs of Helly families of subtrees, Chromaticity of chordal graphs, New insights on \(\mathbf{GA}\)-\(\mathbf H\) reduced graphs, Subpath acyclic digraphs, Exact square coloring of certain classes of graphs: complexity and algorithms, Recognizing interval digraphs and interval bigraphs in polynomial time, Unit hypercube visibility numbers of trees, Modular intersection graphs, Computation of the Shapley value of minimum cost spanning tree games: P-hardness and polynomial cases, On strictly chordality-\(k\) graphs, Intersection graphs of orthodox paths in trees, The lexicographic product of some chordal graphs and of cographs preserves \(b\)-continuity, On the recognition of neighborhood inclusion posets, Parameterized complexity of conflict-free matchings and paths, A width parameter useful for chordal and co-comparability graphs, Characterizing graphs of maximum matching width at most 2, Maximum matching width: new characterizations and a fast algorithm for dominating set, Chordal digraphs, Constant threshold intersection graphs of orthodox paths in trees, Neighborhood inclusion posets and tree representations for chordal and dually chordal graphs, Fugitive-search games on graphs and related parameters, Matching and multidimensional matching in chordal and strongly chordal graphs, A survey on packing colorings, On the tractability of optimization problems on \(H\)-graphs, Subgraph trees in graph theory, Algorithms for induced biclique optimization problems, Maximum independent set and maximum clique algorithms for overlap graphs, Approximation algorithms for geometric conflict free covering problems, Reconfiguration graphs for vertex colourings of chordal and chordal bipartite graphs, A revisit of the scheme for computing treewidth and minimum fill-in, The vertex leafage of chordal graphs, On dominating sets whose induced subgraphs have a bounded diameter, Computing a minimum outer-connected dominating set for the class of chordal graphs, On the vertex ranking problem for trapezoid, circular-arc and other graphs, On the complexity of the black-and-white coloring problem on some classes of perfect graphs, Characterization of 2-path signed network, On spectrum assignment in elastic optical tree-networks, Algorithms for generating strongly chordal graphs, Finding temporal paths under waiting time constraints, Efficiently enumerating minimal triangulations, Efficient enumeration of maximal \(k\)-degenerate induced subgraphs of a chordal graph, Low-congestion shortcut and graph parameters, On the complexity of computing treebreadth, Clique trees of infinite locally finite chordal graphs, Detecting fixed patterns in chordal graphs in polynomial time, Inclusion/exclusion meets measure and conquer, Complexity of distance paired-domination problem in graphs, Weighted domination of independent sets, Towards a comprehensive theory of conflict-tolerance graphs, Tree decompositions with small cost, Strong branchwidth and local transversals, Constant tolerance intersection graphs of subtrees of a tree, Counting maximal independent sets in directed path graphs, Mixing of Markov chains for independent sets on chordal graphs with bounded separators, The complexity of subtree intersection representation of chordal graphs and linear time chordal graph generation, Dyadic representations of graphs, Subexponential parameterized algorithms and kernelization on almost chordal graphs, Representing graphs as the intersection of cographs and threshold graphs, Neighborhood subtree tolerance graphs, On the maximum cardinality cut problem in proper interval graphs and related graph classes, Structural submodularity and tangles in abstract separation systems, Bounds on the bend number of split and cocomparability graphs, Evaluating Datalog via tree automata and cycluits, Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing, Tree-visibility orders, Completeness for intersection classes, Intersection graphs of induced subtrees of any graph and a generalization of chordal graphs, Extending partial representations of subclasses of chordal graphs, Linear-time algorithms for tree root problems, Computing the \(K\)-terminal reliability of directed path graphs, Cliques in the union of graphs, On vertex ranking of a starlike graph, Exact and parameterized algorithms for restricted subset feedback vertex set in chordal graphs, Chordal graphs and their clique graphs, Maximum max-k-clique subgraphs in cactus subtree graphs, Exact algorithms for restricted subset feedback vertex set in chordal and split graphs, Treewidth versus clique number. II: Tree-independence number, Supersolvable saturated matroids and chordal graphs, Directed path graph isomorphism, Recognizing Proper Tree-Graphs, Fugitive-search games on graphs and related parameters, Computing a minimum subset feedback vertex set on chordal graphs parameterized by leafage, Can Romeo and Juliet meet? Or rendezvous games with adversaries on graphs
Cites Work
- Unnamed Item
- On rigid circuit graphs
- Incidence matrices and interval graphs
- Incidence matrices, interval graphs and seriation in archeology
- Intersection representations of graphs by arcs
- Triangulated graphs and the elimination process
- Matrix characterizations of circular-arc graphs
- Representation of a finite graph by a set of intervals on the real line
- Construction of TernaryHv-groups and TernaryP-hyperoperations
- Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph
- A Characterization of Comparability Graphs and of Interval Graphs
