FoCM 2014 conference

Workshop A4 - Graph Theory and Combinatorics

No date set

Characterizations of ($k$)-interval graphs

Florencia Fernández Slezak

Instituto de Cálculo, Facultad de Ciencias Exactas y Naturales, Universidad de Buenos Aires, Argentina   -

Keywords: unit interval graphs, intersection graphs.

A graph $G$ is an interval graph iff its vertices can be put in a one to one correspondence with a family of intervals on the real line such that two vertices in $G$ are adjacent if and only if their corresponding intervals intersect. Such a family of intervals is called an interval model for $G$ [1, 2].

If there is an interval model for graph $G$ such that the intervals are of unit length, then it is called a \emph{unit interval model} and $G$ is a \emph{unit interval graph}. A theorem was proved which establishes that $G$ is a unit interval graph if and only if $G$ is an interval graph containing no induced claw, that is, $K_{1,3}$ [6, 7].

A unit interval graph is an interval graph which admits a representation where all elements have the same length. It is known that a model with intervals of the same length and integer extremes can be built in $\mathcal{O}(n + m)$ time to represent a given unit interval graph [4, 5]. Let $k \in \mathbb{N}_0$, we define $G$ as a ($k$)-interval graph iff $G$ is a unit interval graph which admits a model of open intervals of length $k$ and integer extremes. Likewise, we define the [$k$]-interval graphs as those unit interval graphs which admit a model with the same characteristics but with closed intervals.

In this work, we present a structural characterization of the simplicial vertices in a unit interval graph without twins, which leads to a characterization of the ($k$)-interval graphs. We study the structure of these graphs, finding forbidden induced subgraphs, thus a theorem fully characterising this class is posed, finding the least $k$ such that $G$ is a ($k$)-interval graph.

Moreover, the ($k$)-interval graphs will be studied as induced subgraphs of power of paths, continuing with the results obtained by Lin, Rautenbach, Soulignac and Szwarcfiter [3].

Furthermore, an equivalence between the [$k$]-interval and the ($k$)-interval graphs will be set, which allows us to use the obtained results for open intervals as well as closed intervals.

Finally, we will present open problems we are studying at the moment.


[1] Golumbic, M. C., Algorithmic graph theory and perfect graphs, Academic Press New York (1980)

[2] Lekkerkerker, C. and Boland, D., Representation of finite graphs by a set of intervals on the real line, FundMath, 51, 45--64 (1962).

[3] Lin, M. C., Rautenbach, D., Soulignac, F., Szwarcfiter, J. L., Powers of Cycles, Powers of Paths, and Distance Graphs, Discrete Applied Mathematics, 159, 621--627 (2011).

[4] Lin, M. C., Soulignac, F. J., Szwarcfiter, J. L., Short Models for Unit Interval Graphs, Electronic Notes in Discrete Mathematics, Amsterdam, 35, 247--255 (2009).

[5] Corneil, D. G., Kim, H., Natarajan, S., Olariu, S., Sprague, A. P., Simple linear time recognition of unit interval graphs, Information Processing Letters, 55, 99--104 (1995).

[6] Roberts, F. S., Indifference graphs, in: Proof Techniques in Graph Theory, Proc. Second Ann Arbor Graph Theory Conf., Ann Arbor, Mich., Academic Press, New York, 139--146 (1968).

[7] Gardi, F., The Roberts characterization of proper and unit interval graphs, Discrete Mathematics, 22(307), 2906 -- 2908 (1968).

Joint work with Guillermo Durán (Universidad de Buenos Aires and Universidad de Chile), Luciano Grippo (Universidad Nacional de General Sarmiento), Fabiano Oliveira (Universidade do Estado do Rio de Janeiro) and Jayme Szwarcfiter (Universidade Federal do Rio de Janeiro).

View abstract PDF