Tolerance graphs

DOI10.1016/0166-218X(84)90016-7zbMath0547.05054OpenAlexW4213116309WikidataQ106106890 ScholiaQ106106890MaRDI QIDQ798675

Martin Charles Golumbic, William T. jun. Trotter, Clyde l. Monma

Publication date: 1984

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0166-218x(84)90016-7

zbMATH Keywords

comparability graph perfect graphs interval graph bounded tolerance graph

Mathematics Subject Classification ID

Structural characterization of families of graphs (05C75) Graph theory (05C99)

Related Items (69)

NeST graphs ⋮ Minimal triangulations of graphs: a survey ⋮ Bipartable graphs ⋮ On randomized stopping points and perfect graphs ⋮ Bipartite tolerance orders ⋮ Alternating orientation and alternating colouration of perfect graphs ⋮ Chordal probe graphs ⋮ A note on tolerance graph recognition ⋮ A class of graphs each tolerance graph of which is a bounded one ⋮ The $p$-intersection number of a complete bipartite graph and orthogonal double coverings of a clique ⋮ Proper and unit tolerance graphs ⋮ Computing a dominating pair in an asteroidal triple-free graph in linear time ⋮ Pairwise Compatibility Graphs: A Survey ⋮ Generalized neighbourhoods and a class of perfectly orderable graphs ⋮ Fuzzy intersection graphs ⋮ Double-threshold permutation graphs ⋮ Any complete preference structure without circuit admits an interval representation ⋮ Trapezoid graphs and their coloring ⋮ Weak bipolarizable graphs ⋮ Algorithmic aspects of intersection graphs and representation hypergraphs ⋮ Triangulating graphs without asteroidal triples ⋮ Recognizing graphs without asteroidal triples ⋮ Query-competitive sorting with uncertainty ⋮ On the perfect orderability of unions of two graphs ⋮ Proper and unit bitolerance orders and graphs ⋮ On $k$-weak orders: Recognition and a tolerance result ⋮ Cliques that are tolerance digraphs ⋮ Intuitionistic fuzzy tolerance graphs with application ⋮ Generalizations of semiorders: A review note ⋮ Recognizing simple-triangle graphs by restricted 2-chain subgraph cover ⋮ Recognizing Threshold Tolerance Graphs in $$O(n^2)$$ Time ⋮ A recognition algorithm for simple-triangle graphs ⋮ Triangulating multitolerance graphs ⋮ On the intersection of tolerance and cocomparability graphs ⋮ A sufficient condition for boundedness of tolerance graphs ⋮ Asteroidal triple-free graphs ⋮ On linear and circular structure of (claw, net)-free graphs ⋮ Fuzzy $\phi$-tolerance competition graphs ⋮ On strict (outer-)confluent graphs ⋮ A new graph parameter to measure linearity ⋮ Hereditary dominating pair graphs ⋮ Representations of graphs and networks (coding, layouts and embeddings) ⋮ Stability number and chromatic number of tolerance graphs ⋮ A linear time algorithm to compute a dominating path in an AT-free graph ⋮ Linear time algorithms for dominating pairs in asteroidal triple-free graphs ⋮ An intersection model for multitolerance graphs: efficient algorithms and hierarchy ⋮ On a problem concerning tolerance graphs ⋮ First-fit coloring of bounded tolerance graphs ⋮ Towards a comprehensive theory of conflict-tolerance graphs ⋮ Recognition and computation of minimal triangulations for AT-free claw-free and co-comparability graphs ⋮ Constant tolerance intersection graphs of subtrees of a tree ⋮ Domination graphs: Examples and counterexamples ⋮ A characterization of triangle-free tolerance graphs ⋮ Asteroidal triples of moplexes ⋮ Exact leaf powers ⋮ On the L(h, k)‐labeling of co‐comparability graphs and circular‐arc graphs ⋮ Neighborhood subtree tolerance graphs ⋮ New Geometric Representations and Domination Problems on Tolerance and Multitolerance Graphs ⋮ Treelike comparability graphs ⋮ On the semi-perfect elimination ⋮ Dominating the complements of bounded tolerance graphs and the complements of trapezoid graphs ⋮ AT-free graphs: Linear bounds for the oriented diameter ⋮ Bandwidth and density for block graphs ⋮ Characterization of $\mathrm{B}_0$-VPG cocomparability graphs and a 2D visualization of their posets ⋮ Efficient Local Representations of Graphs ⋮ A survey on pairwise compatibility graphs ⋮ Characterization and a 2D Visualization of B$$_{0}$$-VPG Cocomparability Graphs ⋮ Interval graphs and related topics ⋮ Graphs with special neighbourhood orderings of vertices

Cites Work

This page was built for publication: Tolerance graphs