# A Characterization of 2-Tree Proper Interval 3-Graphs

Authors: David E. Brown; Breeann M. Flesch
Journal: Journal of Discrete Mathematics
 (2014)

---

## Abstract

An intervalp-graph is the intersection graph of a collection of intervals which have been colored with p different colors with edges corresponding to nonempty intersection of intervals from different color classes. We characterize the class of 2-trees which are interval 3-graphs via a list of three graphs and three infinite families of forbidden induced subgraphs.


---

## Body

## 1. Introduction

We discuss finite simple graphs which are variations on the well-studied class of interval graphs. Interval graphs have been extensively studied and characterized, and fast algorithms for various problems such as clique number, chromatic number, dominating sets, and many others have been developed. Indeed it is at this point difficult to give a thorough list of references or a single reference with a sufficient representation of even recent work done on or with interval graphs and several of their variants. The variant we consider is as follows. SupposeG is a graph whose vertices correspond to a collection of intervals which is partitioned into some number of color classes with vertices adjacent if and only if their corresponding intervals intersect and belong to different color classes; such a graph is an interval
p
-graph and the collection of intervals (and its partition into color classes) to which vertices correspond will be referred to as a representation. After presenting forbidden induced subgraph results for interval 2-graphs, T.S. Michael posed the following question to the first author: given a graph
G
=
(
V
,
E
)
, what is the minimum positive integer
p
such that a class of intervals partitioned into
p
color classes represents
G
so that vertices are adjacent if and only if their corresponding intervals intersect and are of different color classes? The first author and Dr. Michael quickly realized that some graphs could not be represented for any number of color classes; for example, a 5-cycle and T
3 (see Figure 1) cannot be represented using any number of color classes. Hence when we say “G is not an interval p-graph”, it is not the p that is under contention, since p is always the chromatic number of G, if
G
has a representation, see [1, 2]. This is why when we say “G is an interval p-graph” we mean that G has a representation for some p. When we put in place of p a numeral, say 3, we mean by “G is an interval 3-graph” that G has a representation using 3 or fewer color classes. This nuance in semantics allows us to consider interval p-graphs for characterization via forbidden subgraphs, since otherwise a forbidden subgraph (obtained by vertex deletion) may have a smaller chromatic number but still be representable. The notion of interval p-graphs with p
=
2, that is the interval bigraphs, was first introduced in [3] and has been investigated more recently by Hell and Huang [4, 5], Müller [6], Brown [1], and Das et al. [7] and others mentioned in their references. But for p not necessarily 2, the first paper appears to be by Brown et al. [2], but interval p-graphs have been studied or used in [8, 9]. As far as a characterization via forbidden induced subgraphs is concerned, the only such characterizations for interval p-graphs are for trees, hence p
=
2, (see [10]) and for k-trees, any p (see [11]).Figure 1IfG is an interval p-graph with a representation in which no interval contains another properly, then G is a proper interval
p
-graph. The proper interval 2-graphs have been characterized via many properties and shown to be equivalent to many well-known classes of graphs (see [4, 12]) as well as via a forbidden induced subgraph characterization consisting of three graphs, odd cycles, and all cycles of length six or greater. For example, proper interval 2-graphs are precisely the bipartite permutation graphs, the comparability graphs of posets of dimension at most two, the complements of proper circular arc graphs, and the bounded bipartite tolerance graphs (see [12] or relevant papers from the literature for the definitions). But essentially none of the characterizations of proper interval 2-graph extend to proper interval p-graphs for p
>
2, as the authors show in a companion article to this one [13]. In this article we give a forbidden induced subgraph characterization for proper interval p-graphs which are 2-trees. The list of forbidden induced subgraphs consists of three graphs and three infinite families of graphs (see Figure 6) and complements the following characterization for (not necessarily proper) interval p-graphs.Theorem 1 (see [11]).
LetG be a 2-tree. The graph G has a representation if and only if it contains no subgraph isomorphic to G
i, 1
≤
i
≤
12 from Figure 2.Figure 2
The complete list of forbidden induced subgraphs for2-tree interval p-graphs.We think our results are an illustration of how the complexity of intervalp-graphs increases when p
>
2, in spite of the ostensibly structure-imposing restriction on the representation, and are perhaps an indication of the need for further research. When graph G has a representation in which no interval contains another properly, we will call the representation proper or refer to it as a proper representation.


## 2. Preliminaries

Ak
-tree may be recursively defined as follows.(i)
K
k is a k-tree.
(ii)
LetG be a k-tree; create G
′ by adding a vertex to G adjacent to all the vertices of some K
k of G.
(iii)
G
′ is a k-tree.A graphG is said to be uniquely colorable if there exists exactly one partition of V
(
G
) into r
=
χ
(
G
) color classes, in which case we say G is uniquely
r
-colorable. A graph is chordal if the smallest induced cycle is a 3-cycle. Any k-tree is chordal and hence uniquely (
k
+
1
)-colorable by the following result from [14]. This fact is very useful for our purposes.Theorem 2 (see [14]).
A graphG of order at least k
+
1 is a k-tree if and only if G is chordal and uniquely (
k
+
1
)-colorable.Anasteroidal triple in a graph is a set of three vertices such that between each pair there is a path that does not intersect the neighborhood of the third. There is not much in the literature beyond [1] about proper interval p-graphs, for p
>
2, but in [1] it is shown that they are asteroidal triple free.Theorem 3 (see [1]).
IfG is a proper interval p-graph, then G contains no asteroidal triple.A graph isweakly chordal if it and its complement do not contain a cycle of length greater than four. A graph is perfect if the chromatic number of any induced subgraph is equal to the clique number of that subgraph. Since Hayward proved that weakly chordal graphs are perfect in [15] and Brown et al. proved that interval p-graphs are weakly chordal in [2], we have the following theorem.Theorem 4 (see [2]).
The class of intervalp-graphs is a class of perfect graphs.Note that this is why, in trying to represent graphG as an interval p-graph, the addition of more than χ
(
G
) interval color classes will not yield a representation when χ
(
G
) interval color classes will not.The following facts and the next lemma will provide the basis for our characterization:(i)
a2-tree is uniquely 3-colorable;
(ii)
proper intervalp-graphs are asteroidal triple free;
(iii)
intervalp-graphs are perfect;
(iv)
any subgraph obtained from vertex deletion of an intervalp-graph is an interval p-graph (the property of being an interval p-graph is hereditary).Lemma 5.
Each graph in the infinite family in Figure3 is not a proper interval p-graph.Figure 3
An infinite family of forbidden induced subgraphs for proper intervalp-graphs.Proof.
Assume for contradiction that there is a proper representation forH
k from Figure 3. Without loss of generality, assume that r
x
1
>
r
a and r
x
1
>
r
b. See Figure 4 for an example representation. The vertices y
1 and x
2 are adjacent to neither a nor b and both are of a different color than one of them. Thus since the representation is proper, r
y
1
>
r
x
1 and r
x
2
>
r
x
1. This also forces y
1 to be in the same color class as x
2 to avoid adjacency, since their intervals overlap. Now consider the vertex y
2; because it is adjacent to x
2, it belongs to a different color than y
1. Thus r
y
2
>
r
x
2. We continue this argument and find that r
y
j
>
r
x
j for j
∈
{
1
,
…
,
k
}, and y
j is the same color as x
j
-
1 for j
∈
{
2
,
…
,
k
-
1
}. Both w and v are not adjacent to y
k
-
1 and are not the same color as y
k
-
1, so r
w
>
r
x
k and r
v
>
r
x
k. Thus the intervals for y
k, w, and v all intersect. This is a contradiction since y
k is not in the same color class as either w or v, but is adjacent to neither.Figure 4
The vertical line signifies the contradiction in the proof of Lemma5.Our arguments for the proof of the main theorem will be facilitated by the notion of trapping which we now define and then prove a lemma about the structure of a proper intervalp-graph which involves this notion. Let G be an interval p-graph that is not a proper interval p-graph and let ℐ be a representation for G in which the number of intervals properly contained in others is minimal. Hence ℐ has at least one interval I
y that is properly contained in another interval, say I
v.NowI
v and I
y are either in the same color class or they are not. But in either case, there is structure in G which necessitates intervals I
x and I
z, each of a different color class than I
y, which flank I
y and prevent the extension of either of I
y’s endpoints past either of those of I
v; that is; there is some structure in G which forces G to have no proper representation. What structure this is is not easily named; indeed it is in a sense the purpose of this paper to investigate what prohibits an interval 3-graph from having a representation using intervals with no proper containment among them. The only structural thing we can be sure of is that (1) y
z is not an edge of G, (2) neither is x
y, but (3) v
z and v
x are, and (4) I
x and I
z are of different color classes than I
v and of I
y. If any of those four statements are not true the interval I
y may be adjusted and not contained in I
v. So we have intervals I
x and I
z with I
x
∩
I
v
≠
∅, I
z
∩
I
v
≠
∅, I
y
∩
I
z
=
∅, I
y
∩
I
x
=
∅, and y’s interval is in a different color class than both x’s and z’s. Moreover, there are two neighbors of v, x and z, that are not neighbors of y, and I
x and I
z  trap  I
y in I
v (see 𝒥
1 in Figure 5).Figure 5
Representations used in Lemma6. In 𝒥
2, I
w could be gray or black.Figure 6
The forbidden induced subgraphs for2-trees that are interval 3-graphs.Since intervalp-graphs are perfect, we now restrict the number of color classes to three—the chromatic number of a 2-tree.Lemma 6.
LetG be an interval 3-graph that is not a proper interval 3-graph. Let ℐ be a representation for G with the least containment, and let I
x and I
z trap I
y in I
v. If I
x and I
z are in the same color class, then x must have a neighbor that is not adjacent to z, and z must have a neighbor that is not adjacent to x.Proof.
LetG be an interval 3-graph that is not a proper interval 3-graph. Let ℐ be a representation for G with the least containment, and let I
x and I
z trap I
y in I
v. Assume that x and z are in the same color class. First assume that x and z have the same neighborhood. Since they are the same color class, overlapping intervals do not result in an adjacency. Thus the intervals can be moved so that I
x and I
z overlap and do not trap I
y. This movement of intervals is shown in 𝒥
2 in Figure 5 without I
w. Notice that there is room for the intervals for all of the neighbors of x and z without proper containment. Thus this representation has less interval containment, which is a contradiction.
Now without loss of generality assume thatN
(
z
)
⊊
N
(
x
), and let w
∈
N
(
x
), but w
∉
N
(
z
). Again we can move the intervals because x and z belong to the same color class. If w
∉
N
(
v
), then we can configure the intervals as in 𝒥
2 in Figure 5. Notice that there is still room for the intervals for the common neighbors of x and z without proper containment. If w
∈
N
(
v
), then it must be of the same color as y. Hence we can configure the intervals as in 𝒥
3 in Figure 5, again with room for the neighbors of x and z without proper containment. Thus in either case the representation has less interval containment, which is a contradiction. Therefore x must have a neighbor that is not adjacent to z, and z must have a neighbor that is not adjacent to x.


## 3. Characterization

We are now ready to prove the main result.Theorem 7.
LetG be 2-tree that has a representation. The graph G is a proper interval 3-graph if and only if it contains none of the graphs from Figure 6 as an induced subgraph.Proof.
Assume thatG is a proper interval 3-graph. The graph C from Figure 6 contains an asteroidal triple. Every other subgraph from Figure 6 contains a member of the infinite family of graphs from Figure 3. Thus G cannot contain any of the induced subgraphs listed in Figure 6, since none of them have a proper representations from Theorem 3 and Lemma 5.
Assume for contradiction thatG is not a proper interval 3-graph and does not contain a graph from Figure 6 as an induced subgraph. Since G is an interval 3-graph, consider a representation with the least number of intervals properly contained in another. Label the three colors gray, white, and black, and notice that this is a proper coloring of G. Assume that the interval for vertex v is colored gray and contains the interval for vertex y, which could by any of the three colors. Since this representation has the least number of contained intervals, there must be two nonadjacent vertices whose intervals intersect the interval of v; label them x and z. The vertices x and z are not neighbors of y and are both in a different color class than y.
This gives us12 colorings of x, y, and z: white, gray, and white; white, gray, and black; black, gray, and white; black, gray, and black; white, black, and white; white, black, and gray; gray, black, and white; gray, black, and gray; black, white, and black; black, white, and gray; gray, white, and black; and gray, white, and gray. Since white and black are indistinguishable at this point, we can narrow these 12 colorings down to five different colorings of x, y, and z: white, black, and white; white, gray, and white; white, gray, and black; white, black, and gray; and gray, white, and gray, which we group into three cases.Case  1. The vertices x, y, and z are colored white, black, and white, respectively.BecauseG is a 2-tree, there is a path from x to z that is a subset of the neighborhood of v. This leads us to two subcases: this path includes y or does not include y. First let us assume that this path includes y; label the path   x
,
a
1
,
…
,
a
k
,
y
,
b
1
,
…
,
b
j
,
z. Since this path is contained in the neighborhood of v, the vertices must be all colored white or black. Plus x, y, and z are pairwise nonadjacent, so k
>
0 and j
>
0. Since the coloring is proper, a
1 and b
j must be black and a
k and b
1 must be white, so k
≠
1 and j
≠
1. Hence the graph induced by the vertices {
v
,
x
,
a
1
,
…
,
a
k
,
y
,
b
1
,
…
,
b
j
,
z
} contains B from Figure 6 as an induced subgraph with v
≅
g.Now let us assume that the path fromx to z in the neighborhood of v does not include y; label the path x
,
d
1
,
…
,
d
i
,
z and notice that i
>
0. From Lemma 6, x must have a neighbor that is not adjacent to z and z must have a neighbor that is not adjacent to x; label them   a and b, respectively. If there is a choice for a or b choose the vertex with the shortest distance to v. First assume that a
=
d
1 or b
=
d
i; then i
≥
3, because d
1
,
…
,
d
i must be all black or white. If y is adjacent to a d
j, then 2
≤
j
≤
i
-
1, since d
1
,
d
i, and y are all black. Hence the graph A from Figure 6 is an induced subgraph of {
v
,
y
,
x
,
d
1
,
…
,
d
i
,
z
} with v
≅
g. If y is not adjacent to a d
j, then there is a path from some d
t, 1
≤
t
≤
i, to y in the neighborhood of v; label this path   d
t
,
f
1
,
…
,
f
n
,
y. Hence the graph A from Figure 6 is an induced subgraph of {
v
,
x
,
d
1
,
…
,
d
t
,
…
,
d
i
,
z
,
f
1
,
…
,
f
n
,
y
} with v
≅
g.Now assume thata
≠
d
1 and b
≠
d
i; if i
≥
3 then the argument above holds, so assume that i
<
3. We also know that i
≠
2, because of the coloring, so let i
=
1. Since d
1 and y are both black, n
≥
1. Thus if either a
∈
N
(
v
) or b
∈
N
(
v
), then the graph A from Figure 6 is an induced subgraph of {
a
,
x
,
v
,
d
1
,
f
1
,
…
,
f
n
,
y
,
z
,
b
} with v
≅
g. If a
,
b
∉
N
(
v
), then a
,
b
∈
N
(
d
1
) since we chose a and b to be the shortest distance to v. Therefore, the graph A from Figure 6 is an induced subgraph of {
a
,
x
,
v
,
d
1
,
f
1
,
…
,
f
n
,
y
,
z
,
b
} with d
1
≅
g.Case  2. The vertices x, y, and z are colored white, gray, and white or white, gray, and black, respectively.Label the path fromx to z in the neighborhood of v as d
1
,
…
,
d
i. Notice that y and v are in the same color class, so they are not adjacent. Thus y must have two neighbors that are also adjacent to v, so y must be adjacent to at least one d
j, j
∈
{
1
,
…
,
i
}. First assume that d
j
,
d
k
∈
N
(
y
) for consecutive j and p. Then the graph C from Figure 6 is an induced subgraph of {
x
,
y
,
z
,
d
1
,
…
,
d
i
,
v
}.Now assume that there is only onej
∈
{
1
,
…
,
i
} such that d
j
∈
N
(
y
). There is a path from v to y in the neighborhood of d
j; label it m
1
,
…
,
m
n. If j
∈
{
2
,
…
,
i
-
1
}, then the graph A from Figure 6 is an induced subgraph of {
x
,
y
,
z
,
d
1
,
…
,
d
i
,
v
,
m
1
} with v
≅
g. If not, then without loss of generality, assume that j
=
1. The intervals for the vertices x and d
2 (if i
=
1, then use z instead of d
2) trap the interval for y, so each must have a neighbor which is not adjacent to the other. Consider the neighbors of this type that are the least distance to v and label the neighbor of x as t and the neighbor of d
2 as u. If t
,
u
∈
N
(
v
) then the graph A from Figure 6 is an induced subgraph of {
t
,
x
,
d
1
,
d
2
,
u
,
v
,
m
1
} with v
≅
g. If t
∉
N
(
v
), then the graph A from Figure 6 is an induced subgraph of {
t
,
x
,
d
1
,
d
2
,
v
,
m
1
,
…
,
m
n
,
y
} with d
1
≅
g. A similar argument will find A as an induced subgraph if u
∉
N
(
v
).Case  3. The vertices x, y, and z are colored white, black, and gray or gray, black, and gray, respectively.Sincev and z are both gray, their overlapping intervals do not result in an adjacency. Thus either I
z intersects I
v because there exists a vertex w such that r
w
<
r
v and w
∈
N
(
z
) or l
z
<
r
v so that I
z is not contained in another interval.Consider the first case. Ifr
w
>
r
v, then I
z could be moved so that I
y is not trapped in I
v. Thus there must be a vertex t such that l
t
<
r
v and w
∉
N
(
t
). If t is white or black, then the graph induced by the vertices {
w
,
v
,
z
,
t
} is a cycle of length 4. However this is a contradiction, because 2-trees are chordal. If t is gray either it can be moved so that r
w
>
r
v or I
t is there because of another adjacency. In the former case, we contradict that this representation has minimum containment. In the latter case, we start this case all over again with the vertices x, y, and t. Since G is finite, we eventually end up with the one of the previous two contradictions.Now considerl
z
<
r
v so that I
z is not contained in another interval, which we will label b if it is white and g
1 if it is black. Since I
z is not contained in I
b, I
b
∩
I
y
=
∅. If x is white, then we are in Case 1 with the vertices v, x, y, and b; if x is gray, then we can restart the argument in this case with the vertices v, x, y, and b.BecauseI
z is avoiding containment in I
g
1, I
g
1 must intersect an interval for a white or black vertex that is not a neighbor of z. If this neighbor is white, then we label it   b. If it is gray, then label it   r
1. Notice that g
1 and r
1 are not adjacent, so they must share a gray neighbor (since we already considered the case with a white neighbor), label this neighbor   g
2. Again the intervals could be reordered to create a representation with less containment, unless I
g
2 intersects a gray or white interval. If it is white, then we again label it   b. If it is gray, then we label it   r
2 and notice that there must be a g
3 that is adjacent to both g
2 and r
2 (see I
1 in Figure 7). The gray and black intervals could again be reorganized with less containment (see I
2 in Figure 7) unless there is another neighbor. The black and gray intervals continue in this way until we eventually add a white interval, which we label  b. Thus if x is white the graph induced by the vertices {
x
,
y
,
z
,
v
,
g
1
,
…
,
g
k
,
r
1
,
…
,
r
k
-
1
,
b
} has the structure of K
1 from Figure 8, where g
k could be black or gray. If x is gray then we get the black and gray structure of {
g
1
,
…
,
g
k
,
r
1
,
…
,
r
k
-
1
} on the left hand side of v until we hit a white vertex on the left. In either case, the graph has the structure of K
1.Figure 7
The interval forx could be gray or white.Figure 8Let us first consider the subgraph ofK
1 in Figure 8 induced by the vertices {
x
,
y
,
v
,
g
1
} (or similarly {
g
k
-
1
,
g
k
,
b
,
r
k
-
1
}). There is a path from x to g
1 in the neighborhood of v; label it   v
1
,
…
,
v
a. If a
>
4, then the graph B from Figure 6 is an induced subgraph of {
x
,
v
,
g
1
,
v
1
,
…
,
v
a
} with v
≅
g, so a
≤
4. Because of coloring a must be even, so either a is two or four. If a is four, then the graph induced by the vertices {
x
,
v
,
g
1
,
v
1
,
v
2
,
v
3
,
v
4
} is isomorphic to the left end of K
2 in Figure 8. If a is two, then y
≠
v
j for any j. Thus the graph induced by the vertices {
x
,
v
,
y
,
g
1
,
v
1
,
v
2
} is isomorphic to the right end K
2 in Figure 8.Now consider the structure of the graph around the vertices{
g
i
-
1
,
g
i
,
g
i
+
1
}, 1
≤
i
≤
k
-
1 (g
0
=
v). There is a path from g
i
-
1 to g
i
+
1 in the neighborhood of g
i; label it as  i
1
,
…
,
i
a
i. Since g
i
-
1 and g
i
+
1 are the same color, a
i must be odd for all i. If a
i
=
1 then A from Figure 6 is an induced subgraph of {
g
i
-
1
,
g
i
,
g
i
+
1
,
i
1
,
r
i
-
1
,
(
i
-
1
)
a
i
-
1
,
(
i
+
1
)
1
} with i
1
≅
g. Furthermore, if a
i
≥
5 then B from Figure 6 is an induced subgraph of {
g
i
-
1
,
g
i
,
g
i
+
1
,
i
1
,
…
,
i
a
i
} with g
1
≅
g. Thus a
i
=
3 for all i.Next we show that(
i
-
1
)
3
=
i
1 for all i (including both ends, i.e., v
a
=
1
1). Assume this is not the case and let t be the smallest index i such that (
i
-
1
)
3
≠
i
1. Consider the subgraph T induced by the vertices {
x
,
y
,
z
,
v
,
v
1
,
…
,
v
a
,
g
1
,
1
2
,
1
3
,
g
2
,
2
2
,
2
3
,
…
,
g
t
-
1
,
(
t
-
1
)
2
,
(
t
-
1
)
3
,
g
t
,
t
1
}. If {
x
,
v
,
v
1
,
…
,
v
a
,
g
1
} is isomorphic to the left end of K
2 in Figure 8, then D
t from Figure 6 is an induced subgraph of T. If {
x
,
y
,
v
,
v
1
,
…
,
v
a
,
g
1
} is isomorphic to the right end of K
2 in Figure 8, then E
t from Figure 6 is an induced subgraph of T. Therefore, (
i
-
1
)
3
=
i
1 for all i, which is shown in K
3 in Figure 8.Now we can see that if both ends ofG look like the left end of K
2 in Figure 8, then D
k from Figure 6 is an induced subgraph of G. If both ends of G look like the right end of K
2 in Figure 8, then F
k from Figure 6 is an induced subgraph of G. Lastly if one end looks like the left end and one looks like the right end of K
2 in Figure 8, then E
k from Figure 6 is an induced subgraph of G.In each case we found that a graph from Figure6 is an induced subgraph of G, which is a contradiction. Therefore, if G contains none of the graphs from Figure 6 as an induced subgraph, it is a proper interval 3-graph.If we combine Theorem7 with Theorem 1, we get the following corollary.Corollary 8.
A2-tree is a proper interval 3-graph if and only if it contains none of the graphs from Figure 6 and Figure 2 as an induced subgraph.Combining the above corollary with Theorem2, we get the following.Corollary 9.
A chordal uniquely3-colorable graph is a proper interval 3-graph if and only if it contains none of the graphs from Figure 6 and Figure 2 as an induced subgraph.


## 4. Unit Intervalp-Graphs

Aunit interval graph is an interval graph that can be represented using only intervals of unit length. The following well-known result from Roberts [16] informs us that the class of proper interval graphs is precisely the class of unit interval graphs.Lemma 10 (see [16]).
The unit interval graphs are equivalent to the proper interval graphs, and they are further equivalent to theK
1,3-free interval graphs.Aunit interval
p
-graph is an interval p-graph that can be represented using only intervals of unit length. We will refer to the representation of a unit interval p-graph as a unit representation. When p
=
2 it is known that unit equals proper (see [12, 17]). We prove it now for all p. This proof follows closely a proof from Golumbic and Lipshteyn in [18].Lemma 11.
A graphG is a unit interval p-graph if and only if it is a proper interval p-graph.Proof.
LetG be a unit interval p-graph. Since a unit interval cannot properly contain another unit interval, G is also a proper interval p-graph.
LetG be a proper interval p-graph, and let ℐ be the proper representation of G. Create the graph G
′ such that V
(
G
′
)
=
V
(
G
) and x
y
∈
E
(
G
′
) if I
x
∩
I
y
≠
∅ in ℐ, regardless of color. In other words, G
′ is the graph G with edges added between vertices of the same color class with overlapping intervals in ℐ. Now G
′ is a proper interval graph and from Lemma 10 is also a unit interval graph. Let ℐ
u be the unit interval representation for G
′. If we add the color partition of G to ℐ
u, it is a unit interval representation of G, and thus we are done.Combining Lemma11 with Theorem 7, we get the following.Theorem 12.
LetG be a 2-tree interval 3-graph. Then G is a unit interval 3-graph if and only if it contains none of the graphs from Figure 6 as an induced subgraph.


## 5. Conclusion

In this paper, we have given a characterization of proper interval3-graphs that are 2-trees using their perfection, the absence of asteroidal triples, and in particular their unique colorability. We have noted that for p
=
2 the proper interval p-graphs enjoy many characterizations and equivalence to many classes of graphs, but for p
>
2 their characterizability seems to be more difficult. We believe this is in part due to the fact that bipartite graphs are uniquely 2-colorable and hence there is a forced assignment of intervals to color classes. When studying interval p-graphs with p
>
2 and the graph under consideration is not uniquely colorable, there are certain pathologies which need to be overcome. For example, in Figure 9(I), we have a graph with no unit representation; if the interval color assignment is as indicated, vertices f and b should be adjacent. But, in Figure 9(II), the interval color assignment is conducive to a unit representation.Figure 9
A unit (proper) interval3-graph which requires care in the assignment of interval color classes.However we conjecture that the absence of any graph from the infinite family of graphs in Figure3 and the absence of asteroidal triples completely characterizes proper interval 3-graphs.If we consider proper intervalp-graphs with a higher chromatic number, say 4, we find more forbidden induced subgraphs, including the graphs in Figure 10. Although characterizing all proper interval 4-graphs using forbidden induced subgraphs may be a difficult problem, it would be interesting to restrict the search to a well-known family of graphs, say 3-trees or uniquely 4-colorable graphs.Figure 10
Some forbidden induced subgraphs withχ
(
G
)
=
4.



---

*Source: 143809-2014-02-23.xml*