Topics in Intersection Graph Theory
From MaRDI portal
Publication:4231782
DOI10.1137/1.9780898719802zbMath0945.05003OpenAlexW112858196MaRDI QIDQ4231782
Terry A. McKee, Fred R. McMorris
Publication date: 15 March 1999
Full work available at URL: https://doi.org/10.1137/1.9780898719802
characterizationschordal graphsinterval graphsintersection graphsline graphsthreshold graphscompetition graphs
Research exposition (monographs, survey articles) pertaining to combinatorics (05-02) Enumeration in graph theory (05C30)
Related Items
The adjacency matrix of a graph as a data table: a geometric perspective, Finding a Maximum Clique in a Grounded 1-Bend String Graph, Star coloring of graphs, Characterizing atoms that result from decomposition by clique separators, Archimedean ϕ ‐tolerance graphs, Computing the clique-separator graph for an interval graph in linear time, Characterizing directed path graphs by forbidden asteroids, When every k-cycle has at least f(k) chords, On the intersection graphs of orthogonal line segments in the plane: characterizations of some subclasses of chordal graphs, Topological Classification of RNA Structures via Intersection Graph, Dot product dimensions of graphs, Factoring Boolean functions using graph partitioning, Chordal multipartite graphs and chordal colorings, Automorphism group of the intersection graph of ideals over a matrix ring, Symmetric graph-theoretic roles of two-pairs and chords of cycles, Formulas in connection with parameters related to convexity of paths on three vertices: caterpillars and unit interval graphs, Online Coloring and $L(2,1)$-Labeling of Unit Disk Intersection Graphs, Complete characterization of incorrect orthology assignments in best match graphs, Vertices removal for feasibility of clustered spanning trees, Extending partial representations of interval graphs, New graph classes characterized by weak vertex separators and two-pairs, Unnamed Item, Contact Representations of Planar Graphs: Extending a Partial Representation is Hard, Intersection graphs of orthodox paths in trees, Set labelling vertices to ensure adjacency coincides with disjointness, Intersection Graphs of Rays and Grounded Segments, Proper circular arc graphs as intersection graphs of paths on a grid, On the hyperbolicity constant of circular-arc graphs, On the edge‐biclique graph and the iterated edge‐biclique operator, Clique trees of chordal graphs: leafage and 3-asteroidals, Some new results on Jacobson graphs, Intersection graphs of maximal sub-polygons of \(k\)-lizards, Efficient isomorphism for \(S_d\)-graphs and \(T\)-graphs, Recognition of Polygon-Circle Graphs and Graphs of Interval Filaments Is NP-Complete, Unnamed Item, A characterization of unit interval bigraphs of open and closed intervals, Temporal matching on geometric graph data, The minimum-area spanning tree problem, On the complexity of recognizing Stick, BipHook and max point-tolerance graphs, Unnamed Item, Unnamed Item, Characterization of classical graph classes by weighted clique graphs, Refining the hierarchies of classes of geometric intersection graphs, Characterization of 2-path signed network, Dynamic Distance Hereditary Graphs Using Split Decomposition, Complexity and exact algorithms for vertex multicut in interval and bounded treewidth graphs, Kneser Ranks of Random Graphs and Minimum Difference Representations, Note on p-competition graphs of spiders, MAXIMUM AREA INDEPENDENT SETS IN DISK INTERSECTION GRAPHS, Bearing-only formation control of multi-agent systems in local reference frames, SUBEXPONENTIAL INTERVAL GRAPHS GENERATED BY IMMIGRATION–DEATH PROCESSES, The complete optimal stars-clustering-tree problem, On maximizing clique, clique-Helly and hereditary clique-Helly induced subgraphs, A survey on the Intersection graphs of ideals of rings, On maximizing clique, clique-Helly and hereditary clique-Helly induced subgraphs, An intersection model for multitolerance graphs: efficient algorithms and hierarchy, A kind of intersection graph of vector space, On the Iterated Biclique Operator, Geodeticity of the contour of chordal graphs, Toll convexity, THE INTERSECTION GRAPH OF GAMMA SETS IN THE TOTAL GRAPH OF A COMMUTATIVE RING-I, SOME RESULTS ON THE INTERSECTION GRAPHS OF IDEALS OF RINGS, Totally positive matrices and totally positive hypergraphs, A polynomial solution to the \(k\)-fixed-endpoint path cover problem on proper interval graphs, Intersection graphs of non-crossing paths, Unnamed Item, The Longest Path Problem is Polynomial on Cocomparability Graphs, From Path Graphs to Directed Path Graphs, A Fully Dynamic Graph Algorithm for Recognizing Proper Interval Graphs, A new family of proximity graphs: class cover catch digraphs, Enumeration and maximum number of maximal irredundant sets for chordal graphs, Maxclique and unit disk characterizations of strongly chordal graphs, Strengthening strongly chordal graphs, Simple Geometrical Intersection Graphs, Ptolemaic Graphs and Interval Graphs Are Leaf Powers, Unnamed Item, The parameterized complexity of cycle packing: indifference is not an issue, Hardness and structural results for half-squares of restricted tree convex bipartite graphs, On clique coverings of complete multipartite graphs, A NEW CLASS OF WEAKLY PERFECT GRAPHS ATTACHED TO S-ACTS, Unnamed Item, Split Clique Graph Complexity, Characterizing path graphs by forbidden induced subgraphs, Requiring chords in cycles, Bayesian networks: the minimal triangulations of a graph, Planar drawings of fixed-mobile bigraphs, Finding a Maximum-Weight Convex Set in a Chordal Graph, Packing of (0, 1)-matrices, Efficient Local Representations of Graphs, The numbers of shared upper bounds determine a poset, TREE DIAGRAMS FOR STRING LINKS, Efficiently decomposing, recognizing and triangulating hole-free graphs without diamonds, WHEN ALL MINIMAL VERTEX SEPARATORS INDUCE COMPLETE OR EDGELESS SUBGRAPHS, Extending partial representations of subclasses of chordal graphs, Distance Labeling for Permutation Graphs, Chordally signed graphs, Quasi-median graphs from sets of partitions, On the iterated edge-biclique operator, On the computational complexity of 2-interval pattern matching problems, Biclique comparability digraphs of bipartite graphs and minimum ranks of partial matrices, Chordal probe graphs, Hyperplanes of Squier's cube complexes, Random subcube intersection graphs. I: Cliques and covering, Forced pairs in \(A\)-Stick graphs, The dynamic team forming problem: throughput and delay for unbiased policies, 3-coloring arrangements of line segments with 4 slopes is hard, Intersection graphs of cyclic subgroups of groups, Embedding ray intersection graphs and global curve simplification, Hypergraph representation via axis-aligned point-subspace cover, A note on path domination, Towards a characterization of leaf powers by clique arrangements, Double-threshold permutation graphs, On neighborhood-Helly graphs, Recognizing and representing proper interval graphs in parallel using merging and sorting, Strict chordal digraphs viewed as graphs with distinguished edges, Homothetic polygons and beyond: maximal cliques in intersection graphs, On the number of maximal independent sets in minimum colorings of split graphs, A new analysis of quasianalysis, Maximal pivots on graphs with an application to gene assembly, Adjacency matrices of probe interval graphs, A note on sparseness conditions on chordless vertices of cycles, Recognizing simple-triangle graphs by restricted 2-chain subgraph cover, Split clique graph complexity, Constant threshold intersection graphs of orthodox paths in trees, The niche graphs of bipartite tournaments, A recognition algorithm for simple-triangle graphs, Parikh word representability of bipartite permutation graphs, A new characterization of unichord-free graphs, Biclique covers and partitions, Kneser ranks of random graphs and minimum difference representations, On graphs of bounded semilattices, Finding intersection models: from chordal to Helly circular-arc graphs, Characterising circular-arc contact \(B_0\)-VPG graphs, Clique separator decomposition of hole-free and diamond-free graphs and algorithmic consequences, Requiring that minimal separators induce complete multipartite subgraphs, The longest path problem is polynomial on cocomparability graphs, Forbidden induced subgraphs for bounded \(p\)-intersection number, Split decomposition and graph-labelled trees: characterizations and fully dynamic algorithms for totally decomposable graphs, Characterization and representation problems for intersection betweennesses, Subgraph trees in graph theory, Almost every graph is divergent under the biclique operator, On orthogonal ray trees, Interval graph limits, An approach to solving \(A^{k}=J-I\), The recognition of triangle graphs, A fully dynamic graph algorithm for recognizing interval graphs, The composition of semi-finished inventories at a solid board plant., Approximating the 2-interval pattern problem, Characterizing and computing the structure of clique intersections in strongly chordal graphs, The maximum edit distance from hereditary graph properties, Biclique cover and local clique cover of graphs, Tractabilities and intractabilities on geometric intersection graphs, The double competition hypergraph of a digraph, Fixed cardinality stable sets, Obstructions to convexity in neural codes, Dominating sequences in grid-like and toroidal graphs, Convex and isometric domination of (weak) dominating pair graphs, The P versus NP-complete dichotomy of some challenging problems in graph theory, Towards a comprehensive theory of conflict-tolerance graphs, Separator orders in interval, cocomparability, and AT-free graphs, Graphs with the maximum or minimum number of 1-factors, Rooted directed path graphs are leaf powers, On cover-structure graphs, Dimension-2 poset competition numbers and dimension-2 poset double competition numbers, Constant tolerance intersection graphs of subtrees of a tree, Obstacle numbers of graphs, Enumeration of the perfect sequences of a chordal graph, Exact leaf powers, The complexity of subtree intersection representation of chordal graphs and linear time chordal graph generation, A simple algorithm to find Hamiltonian cycles in proper interval graphs, Dyadic representations of graphs, Reconstructing pedigrees: a stochastic perspective, Interval \(k\)-graphs and orders, A vertex ordering characterization of simple-triangle graphs, Paired threshold graphs, On the distribution of the domination number for random class cover catch digraphs, The complexity of clique graph recognition, Localized and compact data-structure for comparability graphs, New work for Carnap's quasi-analysis, Cube intersection concepts in median graphs, The clique-separator graph for chordal graphs, Maximum weight independent sets in hole- and co-chair-free graphs, Competition polysemy, The solution of two problems on bound polysemy, Scale free interval graphs, Succinct navigational oracles for families of intersection graphs on a circle, Characterizations and recognition of circular-arc graphs and subclasses: a survey, A dynamic distributed approach to representing proper interval graphs, APX-hardness of domination problems in circle graphs, A new characterization of strongly chordal graphs, Distributed interactive proofs for the recognition of some geometric intersection graph classes, Hyperbolic bridged graphs, Intersection graphs of maximal hypercubes, On the isomorphism problem for Helly circular-arc graphs, A SLLN for a one-dimensional class cover problem
