Completion of the Mixed Unit Interval Graphs Hierarchy

DOI10.1007/978-3-319-17142-5_25zbMATH Open1459.05218arXiv1412.0540OpenAlexW2962834417MaRDI QIDQ2948474FDOQ2948474

Authors: Alexandre Talon, Jan Kratochvíl 

Publication date: 30 September 2015

Published in: Lecture Notes in Computer Science, Journal of Graph Theory (Search for Journal in Brave)

Abstract: We describe the missing class of the hierarchy of mixed unit interval graphs, generated by the intersection graphs of closed, open and one type of half-open intervals of the real line. This class lies strictly between unit interval graphs and mixed unit interval graphs. We give a complete characterization of this new class, as well as quadratic-time algorithms that recognize graphs from this class and produce a corresponding interval representation if one exists. We also mention that the work in arXiv:1405.4247 directly extends to provide a quadratic-time algorithm to recognize the class of mixed unit interval graphs.

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

Recommendations

• Completion of the Mixed Unit Interval Graphs Hierarchy
• The interval graph completion problem for the complete multipartite graphs
• On the interval completion of chordal graphs
• scientific article; zbMATH DE number 5671249
• Mixed unit interval bigraphs

zbMATH Keywords

intersection graphproper interval graphmixed unit interval graphunit interval graph

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph representations (geometric and intersection representations, etc.) (05C62) Structural characterization of families of graphs (05C75)

Cites Work

• 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 (3)

• Semi-proper 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

This page was built for publication: Completion of the Mixed Unit Interval Graphs Hierarchy

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