\documentclass[11pt]{article}
\usepackage[english]{babel}
\usepackage{amsmath,ifthen,color,eurosym}
\usepackage{wrapfig,hyperref,cite}
\usepackage{latexsym,amsthm,amsmath,amssymb,url,cite}
\usepackage{fancyhdr}
\usepackage{graphicx}
\usepackage{stmaryrd,wasysym}
\usepackage{colortbl}
\usepackage[lined,boxed,commentsnumbered]{algorithm2e}
\usepackage[english]{babel}
\usepackage[utf8x]{inputenc}

\def\baselinestretch{1}


\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}
\newtheorem{corollary}{Corollary}
\newtheorem{claim}{Claim}
\newtheorem{observation}{Observation}
\newtheorem{proposition}{Proposition}

\setlength{\textheight}{22cm}
\setlength{\topmargin}{-1cm}
\setlength{\textwidth}{165mm}
\setlength{\oddsidemargin}{-3mm}
\setlength{\unitlength}{1mm}


\renewcommand{\refname}{\small References}
\addto{\captionsenglish}{\renewcommand{\refname}{\normalsize
    References}}



%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%
%Put here the package you need, new commands, ...



%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%

\begin{document}
%1 page max !!

%Write your title here:
\noindent{\bf\Large Completion of the mixed-unit interval graphs hierarchy}

%List the authors as follows (you may underline the speaker, or just
%name the speaker, and mention your co-authors at the end, up to you):
\noindent Alexandre Talon -- {\small ENS Lyon}

\noindent \underline{Jan Kratochvil} -- {\small Charles University, Prague}



\vspace{2ex}

\noindent{\bf Abstract:} %Here write your 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 a polynomial time algorithm to recognize graphs from this class and to produce a corresponding interval representation if one exists.



A graph is an interval graph if one can associate to each of its vertices an interval of the real line such that two vertices are adjacent if and only if the corresponding intervals intersect. A well-studied subclass of the class of interval graphs is the one of proper interval graphs where it is required that no interval properly contains another one. This class coincides with the class of unit interval graphs where all intervals have length one~\cite{roberts}.

However, in this description no particular attention is paid to the types of intervals we use: are they open, closed, or semi-closed?
Dourado and al. proved in \cite{dlprs} that this is of no importance as far as interval graphs are concerned. This is no longer the case, though, for unit interval graphs: deciding which types of intervals are allowed to represent the vertices of a graph is crucial. This fact was notably studied in \cite{roberts,fm,pmunit,dlprs,joos,shuchat}. In these papers one can find results about the classes of graphs we can get depending on the types of unit intervals we allow for their representations. In particular it is shown that if all intervals in a representation are required to be of the same type (all closed, all open, all left-closed-right-open, or all left-open-right-closed), one gets the same class of {\em unit interval graphs} which is a proper subclass of {\em mixed unit interval graphs}, i.e., graphs obtained if no restriction -- apart from the unit length -- on the intervals is imposed. Recently, Joos~\cite{joos} gave a characterization of mixed unit interval graphs by an infinite class of forbidden induced subgraphs, and Shuchat et al.~\cite{shuchat} complemented it by a polynomial-time recognition algorithm.


The aim of this paper is to complete this hierarchy of classes. We consider all subsets of the four types of unit intervals, show that several of them lead to the classic unit interval graphs (where all intervals are closed), recall the previously studied and characterized class determined by open and closed unit intervals, and then show that -- with respect to this parametrization -- there exists exactly one other proper subclass of the class of mixed unit interval graphs. We characterize this class by an infinite list of forbidden induced subgraphs, give a polynomial-time algorithm to check whether a graph belongs to this class, as well as an algorithm to produce an appropriate interval representation of any graph of this class. 
\footnote{The result has been presented at TAMC 2015 in Singapore in May 2015.}


\small
\vspace{-0.2cm}
\begin{thebibliography}{9}

\vspace{-0.1cm}
\bibitem{joos}
F. Joos.
\newblock A Characterization of Mixed Unit Interval Graphs.
\newblock {\em J. Graph Theory} 79(4): 267-281 (2015).


\vspace{-0.1cm}
\bibitem{pmunit}
D. Rautenbach and J.L. Szwarcfiter.
 \newblock Unit Interval Graphs of Open and Closed Intervals.
 \newblock {\em J. Graph Theory} {72}(4), 418-429 (2013).

\vspace{-0.1cm}
\bibitem{dlprs}
M.C. Dourado, V.B. Le, F. Protti, D. Rautenbach, and J.L. Szwarcfiter.
\newblock Mixed unit interval graphs.
\newblock {\em Discrete Math.} {312}, 3357-3363 (2012).

\vspace{-0.1cm}
\bibitem{fm}
P. Frankl and H. Maehara.
\newblock Open interval-graphs versus closed interval-graphs.
\newblock {\em Disc. Math.} {63}:97-100 (1987).

\vspace{-0.1cm}
\bibitem{roberts}
F.S. Roberts.
\newblock Indifference graphs.
\newblock in {\em Proof Techniques in Graph Theory}, pp.139-146 (1969).

\vspace{-0.1cm}
\bibitem{shuchat}
A. Shuchat, R. Shull, A. N. Trenk, and L. C. West
\newblock Unit Mixed Interval Graphs.
\newblock arXiv:1405.4247 (2014).



\end{thebibliography}


\end{document} 