Logo del repository
  1. Home
 
Opzioni

Uniquely orderable interval graphs

Fiori-Carones, Marta
•
Marcone, Alberto
2022
  • journal article

Periodico
DISCRETE MATHEMATICS
Abstract
Interval graphs and interval orders are deeply linked. In fact, edges of an interval graphs represent the incomparability relation of an interval order, and in general, of different interval orders. The question about the conditions under which a given interval graph is associated to a unique interval order (up to duality) arises naturally. Fishburn provided a characterisation for uniquely orderable finite connected interval graphs. We show, by an entirely new proof, that the same characterisation holds also for infinite connected interval graphs. Using tools from reverse mathematics, we explain why the characterisation cannot be lifted from the finite to the infinite by compactness, as it often happens.
DOI
10.1016/j.disc.2022.112935
WOS
WOS:000794945000002
Archivio
http://hdl.handle.net/11390/1224210
info:eu-repo/semantics/altIdentifier/scopus/2-s2.0-85129155683
https://www.sciencedirect.com/science/article/pii/S0012365X22001418
https://ricerca.unityfvg.it/handle/11390/1224210
Diritti
open access
Soggetti
  • Interval graphs Infi...

google-scholar
Get Involved!
  • Source Code
  • Documentation
  • Slack Channel
Make it your own

DSpace-CRIS can be extensively configured to meet your needs. Decide which information need to be collected and available with fine-grained security. Start updating the theme to match your nstitution's web identity.

Need professional help?

The original creators of DSpace-CRIS at 4Science can take your project to the next level, get in touch!

Realizzato con Software DSpace-CRIS - Estensione mantenuta e ottimizzata da 4Science

  • Impostazioni dei cookie
  • Informativa sulla privacy
  • Accordo con l'utente finale
  • Invia il tuo Feedback