On rigid circuit graphs
From MaRDI portal
Publication:773621
DOI10.1007/BF02992776zbMath0098.14703OpenAlexW2035331304WikidataQ56430105 ScholiaQ56430105MaRDI QIDQ773621
Publication date: 1961
Published in: Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf02992776
Related Items
Pushing vertices in digraphs without long induced cycles, A parallel algorithm for computing Steiner trees in strongly chordal graphs, Signed graphs and the freeness of the Weyl subarrangements of type \(B_\ell\), Separation of two convex sets in convexity structures, The parallel solution of domination problems on chordal and strongly chordal graphs, The generating polynomial and Euler characteristic of intersection graphs, The struction algorithm for the maximum stable set problem revisited, Toughness and Hamiltonicity of a class of planar graphs, Dirac's theorem on chordal graphs and Alexander duality, Generating and characterizing the perfect elimination orderings of a chordal graph, Efficient algorithms for minimum weighted colouring of some classes of perfect graphs, Representing a concept lattice by a graph, An efficient parallel algorithm for the minimal elimination ordering (MEO) of an arbitrary graph, Mock threshold graphs, Finding minimum height elimination trees for interval graphs in polynomial time, Clique tree generalization and new subclasses of chordal graphs, Recognizing bull-free perfect graphs, Metric graphs elastically embeddable in the plane, Coloring perfect degenerate graphs, On graphs in which any pair of colour classes but one induces a tree, Cuts, matrix completions and graph rigidity, Planar graphs with least chromatic coefficients, Graph extremities defined by search algorithms, An introduction to clique minimal separator decomposition, Computing a clique tree with the algorithm maximal label search, Characterizations and algorithmic applications of chordal graph embeddings, Universally signable graphs, A note on perfectly orderable graphs, Chromaticity of chordal graphs, Inequalities for free multi-braid arrangements, Recognizing interval digraphs and interval bigraphs in polynomial time, Meyniel weakly triangulated graphs. II: A theorem of Dirac, On the structure and chromaticity of graphs in which any two colour classes induce a tree, A note on perfect orders, An algorithm for coloring some perfect graphs, A note on \(r\)-dominating cliques, On the chromatic uniqueness of the graph \(W(n,n-2,k)\), Finding a sun in building-free graphs, Chordal digraphs, On treewidth and minimum fill-in of asteroidal triple-free graphs, Separability generalizes Dirac's theorem, Retracts and algebraic properties of cut algebras, Sequences of regressions and their independences, Some problems on induced subgraphs, 2-role assignments on triangulated graphs., The regularity of edge ideals of graphs, A note on chromatic number of (cap, even hole)-free graphs, The type defect of a simplicial complex, On simplicial and co-simplicial vertices in graphs., Inheritance principles for chordal graphs, Covering all cliques of a graph, Representations of graphs and networks (coding, layouts and embeddings), Some aspects of the semi-perfect elimination, Surface subgroups of Coxeter and Artin groups., Some properties of graph centroids, Finding large holes, An inertia formula for Hermitian matrices with sparse inverses, Vertex-weighted graphs and freeness of $ \psi $-graphical arrangements, Computational complexity of the vertex cover problem in the class of planar triangulations, Unit interval vertex deletion: fewer vertices are relevant, A linear-time algorithm for isomorphism of a subclass of chordal graphs, On the contour of bipartite graphs, Non-edge orientation and vertex ordering characterizations of some classes of bigraphs, On slim graphs, even pairs, and star-cutsets, Clique trees of infinite locally finite chordal graphs, On minimal vertex separators of dually chordal graphs: properties and characterizations, Studies on hypergraphs. I: Hyperforests, Recognition and computation of minimal triangulations for AT-free claw-free and co-comparability graphs, Tree decompositions with small cost, Strong branchwidth and local transversals, Constant tolerance intersection graphs of subtrees of a tree, An algorithm for testing chordality of graphs, What is reconstruction for ordered sets?, Vertex deletion problems on chordal graphs, Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms, Minimal triangulation of a graph and optimal pivoting order in a sparse matrix, Algorithms on clique separable graphs, A note on perfect Gaussian elimination, Koszul binomial edge ideals of pairs of graphs, The sandwich problem for decompositions and almost monotone properties, \(p\)-competition graphs, Counting clique trees and computing perfect elimination schemes in parallel, Induced matchings, Recognition of some perfectly orderable graph classes, Phylogeny numbers, A class of \(\beta\)-perfect graphs, Minimal vertex separators of chordal graphs, On the semi-perfect elimination, Hypergraphs with cyclomatic number zero, triangulated graphs, and an inequality, Sequential colorings and perfect graphs, \(P_4\)-domination in minimal imperfect graphs, On stable cutsets in graphs, The monadic second-order logic of graphs. VIII: Orientations, The forbidden subgraph characterization of directed vertex graphs, All wheels with two missing consecutive spokes are chromatically unique, A characterisation of rigid circuit graphs, On Tucker vertices of graphs, Pseudo-chordal mixed hypergraphs, The maximum clique problem, Free hyperplane arrangements between \(A_{n-1}\) and \(B_ n\), The k-Domination and k-Stability Problems on Sun-Free Chordal Graphs, Lexbfs-orderings and powers of hhd-free graphs∗, Disjointness graphs of segments in the space, Powers of hhd-free graphs∗, Linear-Time Generation of Random Chordal Graphs, On the cover ideals of chordal graphs, Heroes in Orientations of Chordal Graphs, A New Construction for Cohen–Macaulay Graphs, Some Cohen–Macaulay and Unmixed Binomial Edge Ideals, Convexity in Graphs and Hypergraphs, Koszul Binomial Edge Ideals, Matrices with chordal inverse zero-patterns, Edge erasures and chordal graphs, Local medians in chordal graphs, Unnamed Item, Unnamed Item, Polynomially bounding the number of minimal separators in graphs: reductions, sufficient conditions, and a dichotomy theorem, An nc algorithm to recognize hhd-free graphs, Hereditary Efficiently Dominatable Graphs, Efficient parallel graph algorithms for coarse grained multicomputers and BSP, Finding a maximum minimal separator: graph classes and fixed-parameter tractability, Complexity and approximability of the happy set problem, s-strongly perfect cartesian product of graphs, Incidence matrices with the consecutive 1’s property, Characterizing k-chordal unichord-free graphs, Vertex Ordering Characterizations of Graphs of Bounded Asteroidal Number, Graphs with least number of colorings, Colouring square-free graphs without long induced paths., Fuzzy chordal graphs and its properties, Minimum Average Distance Clique Trees, A simple linear time algorithm for triangulating three-colored graphs, Space-efficient algorithms for reachability in directed geometric graphs, Some results on connected vertex separators, Dirac's theorem and multigraded syzygies, Lower bounds and properties for the average number of colors in the non-equivalent colorings of a graph, ZDP(n) ${Z}_{DP}(n)$ is bounded above by n2−(n+3)∕2 ${n}^{2}-(n+3)\unicode{x02215}2$, Diameter and connectivity of finite simple graphs, On the computational complexity of ordered subgraph recognition, Amalgams and χ-Boundedness, A Characterisation of the Minimal Triangulations of Permutation Graphs, Computing partial hypergraphs of bounded width, Edgewise strongly shellable clutters, On Listing, Sampling, and Counting the Chordal Graphs with Edge Constraints, Probe Ptolemaic Graphs, Componentwise linearity of powers of cover ideals, Graphs with sparsity order at most two: the complex case, A New Class of Graphs That Satisfies the Chen‐Chvátal Conjecture, On the structure of (pan, even hole)‐free graphs, Antimatroids, Betweenness, Convexity, Revisiting Decomposition by Clique Separators, Algorithms for a maximum clique and a maximum independent set of a circle graph, Unnamed Item, Computation in Causal Graphs, Standard graded vertex cover algebras, cycles and leaves, Minimum Fill-In and Treewidth of Split+ ke and Split+ kv Graphs, Two-Player Competitive Diffusion Game: Graph Classes and the Existence of a Nash Equilibrium, Graphs of Separability at Most Two: Structural Characterizations and Their Consequences, t-clique ideal and t-independence ideal of a graph, SURFACE SUBGROUPS OF GRAPH PRODUCTS OF GROUPS, Binary Supersolvable Matroids and Modular Constructions, How to use the minimal separators of a graph for its chordal triangulation, Zero-divisor graphs of Catalan monoid, Domination graphs: Examples and counterexamples, A Localization Approach to Improve Iterative Proportional Scaling in Gaussian Graphical Models, Restricted unimodular chordal graphs, Asteroidal triples of moplexes, Finding houses and holes in graphs, A Separator Theorem for Chordal Graphs, Disjoint clique cutsets in graphs without long holes, Deterministic inverse zero-patterns, Expansions of Chromatic Polynomials and Log-Concavity, Graph transformations preserving the stability number, Graph theory, Polynomial Time Algorithms for Computing a Minimum Hull Set in Distance-Hereditary and Chordal Graphs, \(k\)-power domination in block graphs, Two strikes against perfect phylogeny, A new approach to chordal graphs, Cycle Extendability of Hamiltonian Strongly Chordal Graphs, Wait-free approximate agreement on graphs, Higher chordality: From graphs to complexes, Wait-free approximate agreement on graphs, Exact algorithms for a discrete metric labeling problem, ℱ-WORM colorings of some 2-trees: partition vectors, Linear separation of connected dominating sets in graphs, A Polynomial Delay Algorithm for Enumerating Minimal Dominating Sets in Chordal Graphs, Characterizing path graphs by forbidden induced subgraphs, On some simplicial elimination schemes for chordal graphs, Minimal vertex separators and new characterizations for dually chordal graphs, Bounding the projective dimension of a squarefree monomial ideal via domination in clutters, Powers of the Vertex Cover Ideal of a Chordal Graph, Cohen-Macaulay binomial edge ideals, Unnamed Item, Graph Classes and Forbidden Patterns on Three Vertices, Hamiltonian Chordal Graphs are not Cycle Extendable, When Is a Graph Product of Groups Virtually-Free?, Unnamed Item, Some constructions of $\lambda$-minimal graphs, Polynomially bounded algorithms for locatingp-centers on a tree, Vertex Deletion Problems on Chordal Graphs, Minimal triangulations of graphs: a survey, A vertex incremental approach for maintaining chordality, Graph minors. V. Excluding a planar graph, Castelnuovo-Mumford regularity under reduction processes on graphs and hypergraphs, I/O-efficient algorithms for graphs of bounded treewidth, On local convexity in graphs, Induced cycles in triangle graphs, On basic chordal graphs and some of its subclasses, Chordal editing is fixed-parameter tractable, Vertex rankings of chordal graphs and weighted trees, A fast algorithm for finding an edge-maximal subgraph with a TR-formative coloring, Cohen-Macaulay admissible clutters, On the null-homotopy of bridged graphs, Partial inversion for linear systems and partial closure of independence graphs, Locally perfect graphs, Bridged graphs and geodesic convexity, Chordal graph recognition is in NC, Simplicial nonpositive curvature, Max point-tolerance graphs, A sufficient condition to extend polynomial results for the maximum independent set problem, Efficient parallel algorithms for finding maximal cliques, clique trees, and minimum coloring on chordal graphs, On the Hadwiger's conjecture for graph products, Improving on the maximum likelihood estimators of the means in Poisson decomposable graphical models, Maximal chordal subgraphs, Weak bipolarizable graphs, On diameters and radii of bridged graphs, Simplicial decompositions of graphs: A survey of applications, Recognizing claw-free perfect graphs, Complete intersection toric ideals of oriented graphs and chorded-theta subgraphs, Two characterisations of the minimal triangulations of permutation graphs, A Dirac-type characterization of \(k\)-chordal graphs, Regularity of edge ideals of \(C_{4}\)-free graphs via the topology of the lcm-lattice, Homotopy equivalence in finite digital images, Organizing the atoms of the clique separator decomposition into an atom tree, Clique separator decomposition of hole-free and diamond-free graphs and algorithmic consequences, Graphs of separability at most 2, The firefighter problem on graph classes, Critical exponents of graphs, Minimal free resolutions of linear edge ideals, Bounds on the Stanley depth and Stanley regularity of edge ideals of clutters, On the discovery of the cycle-axiom of hypergraphs, On the Colin de Verdière number of graphs, Sphere representations, stacked polytopes, and the Colin de Verdière number of a graph, Combinatorial topology and the global dimension of algebras arising in combinatorics, The competition number of a graph with exactly two holes, Probability distributions with summary graph structure, Centers of triangulated graphs, Fully dynamic algorithm for chordal graphs with \(O(1)\) query-time and \(O(n^2)\) update-time, An optimal greedy heuristic to color interval graphs, Crown-free lattices and their related graphs, Faster parameterized algorithms for \textsc{Minimum Fill-in}, Fair cost allocations under conflicts - a game-theoretic point of view -, Some properties of edge intersection graphs of single-bend paths on a grid, All 4-edge-connected HHD-free graphs are \({\mathbb{Z}}_3\)-connected, Dirac's theorem on simplicial matroids, Local topology of the free complex of a two-dimensional generalized convex shelling, Characterizing and computing the structure of clique intersections in strongly chordal graphs, Shellable quasi-forests and their \(h\)-triangles, A note on lexicographic breadth first search for chordal graphs, New results on Ptolemaic graphs, Stability of Betti numbers under reduction processes: towards chordality of clutters, Complexity of simplicial homology and independence complexes of chordal graphs, More bounds for the Grundy number of graphs, Learning discrete decomposable graphical models via constraint optimization, Which claw-free graphs are perfectly orderable?, On the SPANNING \(k\)-TREE problem, Chordal Coxeter groups., Betti numbers of chordal graphs and \(f\)-vectors of simplicial complexes, A constant approximation algorithm for the densest \(k\)-subgraph problem on chordal graphs, Treewidth computations. I: Upper bounds, Helly theorems for 3-Steiner and 3-monophonic convexity in graphs, On right-angled Artin groups without surface subgroups., How is a chordal graph like a supersolvable binary matroid?, On listing, sampling, and counting the chordal graphs with edge constraints, Independence complexes of chordal graphs, On split-coloring problems, On compact and efficient routing in certain graph classes, Cohen-Macaulay monomial ideals of codimension 2, Enumerating minimal dominating sets in chordal graphs, Special eccentric vertices for the class of chordal graphs and related classes, A linear time recognition algorithm for proper interval graphs, Extending cycles in graphs, The clique-separator graph for chordal graphs, The competition number of a graph with exactly \(h\) holes, all of which are independent, Licci binomial edge ideals, Totally balanced dissimilarities, On 2-walks in chordal planar graphs, Estimating high-dimensional intervention effects from observational data, The strong perfect graph conjecture: 40 years of attempts, and its resolution, Characterizations of strongly chordal graphs, Some aspects of perfect elimination orderings in chordal graphs, A characterization of graphs of competition number m, On powers and centers of chordal graphs, On the representation of triangulation graphs in trees, No graph has a maximal 3-ring of bonds, Weakly triangulated graphs, Counting labelled chordal graphs, Decomposition by clique separators, Penta-extensions of hereditary classes of graphs, The dense amalgam of metric compacta and topological characterization of boundaries of free products of groups, Proving a conjecture on chromatic polynomials by counting the number of acyclic orientations, Coloring rings, Clique‐width: Harnessing the power of atoms, Chordal and perfect zero-divisor graphs of posets and applications to graphs associated with algebraic structures, Right‐angled Artin pro‐p$p$ groups, Coloring \((4K_1,C_4,C_6)\)-free graphs, Behaviors of pairs of dimensions and depths of edge ideals, Computing and listing avoidable vertices and paths, Exact and parameterized algorithms for restricted subset feedback vertex set in chordal graphs, MAT-free graphic arrangements and a characterization of strongly chordal graphs by edge-labeling, Chordal graphs and their clique graphs, Cycle intersection in spanning trees: a shorter proof of a conjecture and applications, Dirac's theorem on chordal graphs implies Brooks' theorem, Exact algorithms for restricted subset feedback vertex set in chordal and split graphs, Approximating the chromatic polynomial of a graph, Dually chordal graphs, Treewidth versus clique number. II: Tree-independence number, Supersolvable saturated matroids and chordal graphs, Subadditivity, strand connectivity and multigraded Betti numbers of monomial ideals, Computing and listing avoidable vertices and paths, On 3-degree 4-chordal graphs, On integer linear programs for treewidth based on perfect elimination orderings, On domination elimination orderings and domination graphs, Chordal matroids arising from generalized parallel connections, Simplicial orders and chordality, Distance \(r\)-domination number and \(r\)-independence complexes of graphs, A note on independence complexes of chordal graphs and dismantling, A necessary condition for the equality of the clique number and the convexity number of a graph, Optimal decomposition by clique separators, An \(O( n^{3})\)-time recognition algorithm for hhds-free graphs, The story of perfectly orderable graphs, Graphs with a unique maximum independent set up to automorphisms, Sequential and parallel triangulating algorithms for elimination game and new insights on minimum degree, Dot product dimensions of graphs, Drawings of planar graphs with few slopes and segments, Graph searches and their end vertices, The DP color function of joins and vertex-gluings of graphs, Characterizations of \((4 K_1,C_4,C_5)\)-free graphs, The existence of a pure Nash equilibrium in the two-player competitive diffusion game on graphs having chordality, The (theta, wheel)-free graphs. I: Only-prism and only-pyramid graphs, The (theta, wheel)-free graphs. II: Structure theorem, Perfect elimination orderings for symmetric matrices, The Hadwiger number, chordal graphs and \(ab\)-perfection, Toric chordality, On the phylogeny graphs of degree-bounded digraphs, On strictly chordality-\(k\) graphs, Forbidden induced subgraphs, 1-perfectly orientable \(K_4\)-minor-free and outerplanar graphs, Solving the clique cover problem on (bull, \(C_4\))-free graphs, A hierarchy of dismantlings in graphs, Decomposable clutters and a generalization of Simon's conjecture, Clique coverings and claw-free graphs, On coherence of graph products of groups and Coxeter groups, Average Betti numbers of induced subcomplexes in triangulations of manifolds, Bounds on regularity of quadratic monomial ideals, A note on the edge cover number and independence number in hypergraphs, Erdős-Ko-Rado theorems for chordal graphs and trees, Classes of perfect graphs, Reconfiguration graphs for vertex colourings of chordal and chordal bipartite graphs, Some results on the target set selection problem, Avoidable paths in graphs, A linear time algorithm for minimum fill-in and treewidth for distance hereditary graphs, On the complexity of the black-and-white coloring problem on some classes of perfect graphs, Modular construction of free hyperplane arrangements, Moplex orderings generated by the LexDFs algorithm, Subset feedback vertex sets in chordal graphs, \(b\)-vectors of chordal graphs, On the correspondence between tree representations of chordal and dually chordal graphs, Searching for better fill-in, Homological shift ideals, Non-ridge-chordal complexes whose clique complex has shellable Alexander dual, A better upper bound on the chromatic number of (cap, even-hole)-free graphs, Efficiently enumerating minimal triangulations, Linear resolutions of quadratic monomial ideals, Detecting fixed patterns in chordal graphs in polynomial time, On guarding the vertices of rectilinear domains, Upper bounds for the regularity of powers of edge ideals of graphs, On the strong chromatic index and maximum induced matching of tree-cographs, permutation graphs and chordal bipartite graphs, Tree decomposition and discrete optimization problems: a survey, Monomial ideals, edge ideals of hypergraphs, and their graded Betti numbers, Skew partitions in perfect graphs, Toll convexity, Minimum fill-in of sparse graphs: kernelization and approximation, Formulas for counting acyclic digraph Markov equivalence classes, Cohen--Macaulay chordal graphs, Representation characterizations of chordal bipartite graphs, A conjecture on triangles of graphs, On the triangle clique cover and \(K_t\) clique cover problems, Completing colored graphs to meet a target property, On axioms constituting the foundation of hypergraph theory, Two classes of \(\beta \)-perfect graphs that do not necessarily have simplicial extremes, A note on simplicial cliques, Vertex elimination orderings for hereditary graph classes, Bass-Serre theory for Lie algebras: a homological approach, Junction trees of general graphs, Matching trees for simplicial complexes and homotopy type of devoid complexes of graphs, Chordality, \(d\)-collapsibility, and componentwise linear ideals, Ambush cops and robbers, The intersection of two vertex coloring problems, On the maximum cardinality cut problem in proper interval graphs and related graph classes, Colouring exact distance graphs of chordal graphs, An improved exact algorithm for minimum dominating set in chordal graphs, On the Lovász-Schrijver PSD-operator on graph classes defined by clique cutsets, Triangulated graphs and the elimination process, Avoidable vertices and edges in graphs: existence, characterization, and applications, Anti-blocking polyhedra, DP color functions versus chromatic polynomials, Structural submodularity and tangles in abstract separation systems, Colouring square-free graphs without long induced paths, The intersection graphs of subtrees in trees are exactly the chordal graphs, Inductive \(k\)-independent graphs and \(c\)-colorable subgraphs in scheduling: a review, Oracles for vertex elimination orderings, Bayesian networks: the minimal triangulations of a graph, Probabilistic pursuits on graphs, Betti numbers of fat forests and their Alexander dual, A generalization of the theorem of Lekkerkerker and Boland, Generalized chordality, vertex separators and hyperbolicity on graphs, Convex geometries over induced paths with bounded length, The competition number of a graph having exactly one hole, A de Bruijn-Erdős theorem for chordal graphs, Efficiently decomposing, recognizing and triangulating hole-free graphs without diamonds, Linear-time algorithms for tree root problems, Supersolvability and freeness for \(\psi\)-graphical arrangements, On graphs with equal total domination and Grundy total domination numbers
Cites Work
