String graphs. I: The number of critical nonstring graphs is infinite
From MaRDI portal
Publication:1121917
DOI10.1016/0095-8956(91)90090-7zbMath0675.05058OpenAlexW1983826065MaRDI QIDQ1121917
Publication date: 1991
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(91)90090-7
Extremal problems in graph theory (05C35) Structural characterization of families of graphs (05C75) Graph theory (05C99)
Related Items
Generalized disk graphs ⋮ Decidability of string graphs ⋮ String graphs. II: Recognizing string graphs is NP-hard ⋮ On Strict (Outer-)Confluent Graphs ⋮ Degeneracy of \(P_t\)-free and \(C_{\geq t}\)-free graphs with no large complete bipartite subgraphs ⋮ Intersection Graphs of Rays and Grounded Segments ⋮ Computing list homomorphisms in geometric intersection graphs ⋮ On strict (outer-)confluent graphs ⋮ Coloring Hasse diagrams and disjointness graphs of curves ⋮ On String Graph Limits and the Structure of a Typical String Graph ⋮ Refining the hierarchies of classes of geometric intersection graphs ⋮ An algorithm for the maximum weight independent set problem on outerstring graphs ⋮ Well quasi orders in subclasses of bounded treewidth graphs and their algorithmic applications ⋮ Hierarchical partial planarity ⋮ Recognizing string graphs in NP ⋮ General lower bounds for the minor crossing number of graphs ⋮ The Complexity of Several Realizability Problems for Abstract Topological Graphs ⋮ Subexponential-time algorithms for finding large induced sparse subgraphs ⋮ Computing maximum independent set on outerstring graphs and their relatives ⋮ Subexponential algorithms for variants of the homomorphism problem in string graphs ⋮ Maximum Independent Set in 2-Direction Outersegment Graphs ⋮ Bounds on the bend number of split and cocomparability graphs ⋮ String graphs of k-bend paths on a grid ⋮ Outerstring Graphs are $\chi$-Bounded ⋮ Efficient Local Representations of Graphs ⋮ Partial Characterizations of 1‐Perfectly Orientable Graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Weakly transitive orientations, Hasse diagrams and string graphs
- String graphs. II: Recognizing string graphs is NP-hard
- Comparability graphs and intersection graphs
- Intersection graphs of curves in the plane
- A recognition algorithm for the intersection graphs of paths in trees
- Graph minors. XVIII: Tree-decompositions and well-quasi-ordering
- Energy, central charge, and the BPS bound for \(1+1\)-dimensional supersymmetric solitons
- Graph minors. XIII: The disjoint paths problem
- The intersection graphs of subtrees in trees are exactly the chordal graphs
- Topology of Thin Film RC Circuits
- Transitive Orientation of Graphs and Identification of Permutation Graphs
- A Characterization of Comparability Graphs and of Interval Graphs
