Representation of a finite graph by a set of intervals on the real line
From MaRDI portal
Publication:3290351
DOI10.4064/FM-51-1-45-64zbMath0105.17501OpenAlexW1517921658MaRDI QIDQ3290351
Jan Ch. Boland, C. Gerrit Lekkerkerker
Publication date: 1962
Published in: Fundamenta Mathematicae (Search for Journal in Brave)
Full work available at URL: https://eudml.org/doc/213681
Related Items (only showing first 100 items - show all)
Maximum Semiorders in Interval Orders ⋮ Extremal Values of the Interval Number of a Graph ⋮ Monotonic Representations of Outerplanar Graphs as Edge Intersection Graphs of Paths on a Grid ⋮ Unnamed Item ⋮ Distance approximating spanning trees ⋮ Characterizing directed path graphs by forbidden asteroids ⋮ Unnamed Item ⋮ Computing a dominating pair in an asteroidal triple-free graph in linear time ⋮ Connected domination and steiner set on asteroidal triple-free graphs ⋮ Linear-Time Algorithms for Finding Tucker Submatrices and Lekkerkerker--Boland Subgraphs ⋮ Characterizing circular-arc graphs ⋮ Reconstruction of Interval Graphs ⋮ Independent sets in asteroidal triple-free graphs ⋮ Query-competitive sorting with uncertainty ⋮ Incidence matrices with the consecutive 1’s property ⋮ Tverberg-type theorems with altered intersection patterns (nerves) ⋮ Vertex Ordering Characterizations of Graphs of Bounded Asteroidal Number ⋮ Minimal Obstructions for Partial Representations of Interval Graphs ⋮ A Characterization of Mixed Unit Interval Graphs ⋮ Computing list homomorphisms in geometric intersection graphs ⋮ A Model for Birdwatching and other Chronological Sampling Activities ⋮ Two new characterizations of path graphs ⋮ The diameter of AT‐free graphs ⋮ Polynomial Kernel for Interval Vertex Deletion ⋮ Partial Characterizations of Circular-Arc Graphs ⋮ Clique trees of chordal graphs: leafage and 3-asteroidals ⋮ Erdős–Pósa property of obstructions to interval graphs ⋮ Deletion to scattered graph classes. II: Improved FPT algorithms for deletion to pairs of graph classes ⋮ Minimum Eccentricity Shortest Path Problem: An Approximation Algorithm and Relation with the k-Laminarity Problem ⋮ On Local Structures of Cubicity 2 Graphs ⋮ Axiomatic characterization of the toll walk function of some graph classes ⋮ Round-competitive algorithms for uncertainty problems with parallel queries ⋮ Asteroidal triple-free graphs ⋮ On characterizing proper max-point-tolerance graphs ⋮ Path eccentricity of graphs ⋮ On Listing, Sampling, and Counting the Chordal Graphs with Edge Constraints ⋮ Unnamed Item ⋮ Resolving prime modules: the structure of pseudo-cographs and galled-tree explainable graphs ⋮ Unnamed Item ⋮ Online coloring of short intervals ⋮ Strong Cocomparability Graphs and Slash-Free Orderings of Matrices ⋮ On the enumeration of interval graphs ⋮ Counting Interval Graphs ⋮ Unnamed Item ⋮ Bipartite Analogues of Comparability and Cocomparability Graphs ⋮ Min-Orderable Digraphs ⋮ The caterpillar-packing polytope ⋮ Treewidth and pathwidth of permutation graphs ⋮ 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 caterpillar-packing polytope ⋮ Linear time algorithms for dominating pairs in asteroidal triple-free graphs ⋮ Total domination in interval graphs ⋮ Hypergraphs and intervals ⋮ Asteroidal triples of moplexes ⋮ Tree-decompositions of small pathwidth ⋮ Vertex deletion into bipartite permutation graphs ⋮ Intersection graphs of non-crossing paths ⋮ The graphs of semirings ⋮ On the L(h, k)‐labeling of co‐comparability graphs and circular‐arc graphs ⋮ Diameter determination on restricted graph families ⋮ Proper Interval Vertex Deletion ⋮ Tree-decompositions of small pathwidth ⋮ Enumeration and maximum number of maximal irredundant sets for chordal graphs ⋮ Two strikes against perfect phylogeny ⋮ Higher chordality: From graphs to complexes ⋮ Complexes of graphs with bounded independence number ⋮ On rectangle intersection graphs with stab number at most two ⋮ Query minimization under stochastic uncertainty ⋮ On the power of BFS to determine a graph's diameter ⋮ Intransitive indifference with unequal indifference intervals ⋮ On nontransitive indifference ⋮ A structure theorem for the consecutive 1's property ⋮ Betweenness, orders and interval graphs ⋮ Linear-Time Recognition of Probe Interval Graphs ⋮ Unnamed Item ⋮ Description of some relations on the set of real-line intervals ⋮ Bounds for the boxicity of Mycielski graphs ⋮ Unrelated Parallel Machine Scheduling Problem with Precedence Constraints: Polyhedral Analysis and Branch-and-Cut ⋮ Partial characterizations of circular-arc graphs ⋮ Characterizing path graphs by forbidden induced subgraphs ⋮ Asteroids in rooted and directed path graphs ⋮ Adjusted Interval Digraphs ⋮ Non-separating cliques, asteroidal number and leafage. The minimal 4-asteroidal split graphs ⋮ Probe interval and probe unit interval graphs on superclasses of cographs ⋮ The Interval Count of a Graph ⋮ The intersection graphs of subtrees in trees are exactly the chordal graphs ⋮ Facet-inducing inequalities with acyclic supports for the caterpillar-packing polytope ⋮ Zdzisław Pawlak, Databases and Rough Sets ⋮ A generalization of the theorem of Lekkerkerker and Boland ⋮ Lexicographic Orientation Algorithms ⋮ d-collapsibility is NP-complete for <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" altimg="si1.gif" overflow="scroll"><mml:mi>d</mml:mi><mml:mo>⩾</mml:mo><mml:mn>4</mml:mn></mml:math> ⋮ Efficient Local Representations of Graphs ⋮ Graph Classes and Forbidden Patterns on Three Vertices ⋮ Independent packings in structured graphs ⋮ Asteroidal Triple of Edges in Bichordal Graphs: A Complete list ⋮ Asteroidal Chromatic Number of a Graph ⋮ Helly-type problems ⋮ Transitiv orientierbare Graphen ⋮ An integer programming approach for the 2-schemes strip cutting problem with a sequencing constraint
This page was built for publication: Representation of a finite graph by a set of intervals on the real line
