A Characterization of Mixed Unit Interval Graphs

DOI10.1007/978-3-319-12340-0_27zbMATH Open1417.05136arXiv1312.0729OpenAlexW192192601MaRDI QIDQ2945201FDOQ2945201

Authors: Felix Joos 

Publication date: 9 September 2015

Published in: Graph-Theoretic Concepts in Computer Science, Journal of Graph Theory (Search for Journal in Brave)

Abstract: We give a complete characterization of mixed unit interval graphs, the intersection graphs of closed, open, and half-open unit intervals of the real line. This is a proper superclass of the well known unit interval graphs. Our result solves a problem posed by Dourado, Le, Protti, Rautenbach and Szwarcfiter (Mixed unit interval graphs, Discrete Math. 312, 3357-3363 (2012)).

Full work available at URL: https://arxiv.org/abs/1312.0729

Recommendations

• Characterizations for unit interval bigraphs
• scientific article; zbMATH DE number 1990673
• A characterization of uniquely representable interval graphs
• Characterizing interval graphs which are probe unit interval graphs
• Mixed unit interval bigraphs
• Completion of the Mixed Unit Interval Graphs Hierarchy
• Completion of the Mixed Unit Interval Graphs Hierarchy
• A new characterization of proper interval graphs
• scientific article; zbMATH DE number 4095511

zbMATH Keywords

intersection graphproper interval graphunit interval graph

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph representations (geometric and intersection representations, etc.) (05C62)

Cites Work

• A simple 3-sweep LBFS algorithm for the recognition of unit interval graphs
• Algorithmic graph theory and perfect graphs
• Representation of a finite graph by a set of intervals on the real line
• Interval graphs and interval orders
• Title not available (Why is that?)
• Integral mixed unit interval graphs
• Unit interval graphs of open and closed intervals
• Mixed unit interval graphs
• Open-interval graphs versus closed-interval graphs

Cited In (14)

• Fractional weak discrepancy and split semiorders
• Mixed unit interval bigraphs
• Title not available (Why is that?)
• Mixed interval hypergraphs
• Title not available (Why is that?)
• Thin strip graphs
• Mixed unit interval graphs
• \(\mathcal{U}\)-bubble model for mixed unit interval graphs and its applications: the MaxCut problem revisited
• Completion of the Mixed Unit Interval Graphs Hierarchy
• Dimension of restricted classes of interval orders
• Tolerance orders of open and closed unit intervals
• Unit interval graphs of open and closed intervals
• Integral mixed unit interval graphs
• Integral mixed unit interval graphs

This page was built for publication: A Characterization of Mixed Unit Interval Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2945201)