Proper and unit tolerance graphs

DOI10.1016/0166-218X(94)00044-EzbMath0830.05058OpenAlexW2096993714MaRDI QIDQ1894354

Kenneth P. Bogart, Garth Isaak, Larry J. Langley, Peter C. Fishburn

Publication date: 28 January 1996

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

Full work available at URL: https://doi.org/10.1016/0166-218x(94)00044-e

zbMATH Keywords

interval graphtolerance graph

Mathematics Subject Classification ID

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

Related Items

NeST graphs ⋮ Bipartite tolerance orders ⋮ A note on tolerance graph recognition ⋮ 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 ⋮ A recognition algorithm for simple-triangle graphs ⋮ Triangulating multitolerance graphs ⋮ On the intersection of tolerance and cocomparability graphs ⋮ The recognition of triangle graphs ⋮ Representing preferences using intervals ⋮ Counting independent sets in a tolerance graph ⋮ An intersection model for multitolerance graphs: efficient algorithms and hierarchy ⋮ Domination graphs: Examples and counterexamples ⋮ A characterization of interval orders with semiorder dimension two ⋮ Vertex splitting and the recognition of trapezoid graphs ⋮ Obituary: Peter C. Fishburn (1936--2021) ⋮ New Geometric Representations and Domination Problems on Tolerance and Multitolerance Graphs ⋮ Tolerance orders of open and closed unit intervals ⋮ Split semiorders

Cites Work

• Tolerance graphs
• Stability number and chromatic number of tolerance graphs
• General results on tolerance intersection graphs
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item