Tip:
Highlight text to annotate it
X
Welcome to the twenty-third lecture of graph theory. So, today we are going to introduce
a graph class called perfect graphs. The motivation for introducing this graph class is the following
inequality, which we have already seen. So, we know that for every graph chi of G, the
chromatic number of the graph is greater than or equal to omega of G, where omega of G is
the size of the maximum clique number of vertices. And the maximum clique in G the inequality
is very trivial, because each vertex in a clique has to get a different color; so many
colors should be present. Now, the question is, is it the reason for
chromatic number to may high? We had ask this question, we have seen that it is not true;
we had constructed graphs in which triangle free but the chromatic number is arbitrary
high and I had mentioned that we can even ask the shortest cycle in the graph be greater
than some number k, given number k, and still the chromatic number can go arbitrarily high.
So chromatic number being high has nothing to do with the presence of a large clique
and the graph, though the presence of a large clique, can in fact make the chromatic number
higher than the higher than equal to that. On the other hand, even if the clique number
omega of G, is quite small for the graph, the chromatic number can be high.
So, naturally this question arises - for what kind of graphs, can we say that this inequality
is becomes equality? That means, this kind of graphs, does it makes sense to ask, study
the kind of graphs, where chromatic number is equal to omega - the clique number. As
such it does not make much sense, because we can take any graph if chromatic number
of G is equal to, say k, and then what you do is, so this is the graph G, and then you
put a small clique here - K k here - on k vertices. So then you say that, see, here
is a graph, say H, where H equal to G union K k. The clique number will be K k and the
chromatic number will be equal to k. So, we cannot tell anything about the structure of
this H, because G is an arbitrarily graph; in fact, is as good as asking, what is the
structure of the graph with chromatic number k, because this structure… just that we
have this clique here, we cannot tell much about this structure of G, because G is any
graph, it can be any graph with chromatic number k.
So as such this question cannot make sense, so we have to define it the question or ask
the question in such a way that this kind of bad example does not come. So Claude Berge
formulated the following question: he asked, so consider the graphs such that not only for the graph itself, for every induced
sub graph of it, say H is an induced sub graph of G. H is... Then suppose it happens that
chi of H equal to omega of H, not only for… so this also includes this is for all H such
that is an induced sub graph of G. Suppose this inequality holds not only for; remember
that is not only for G it is also for every sub graph. In the case he called that this
graphs can be called perfect graphs, he told he name them perfect graphs.
So, a perfect graph is a graph such that every induced sub graph of it has the property that
its chromatic number is equal to clique number. So if this is the class of perfect graph as
he defined; so graph G is perfect if chi of H is equal to omega of H, for every induced
sub graph H of G. Now he asked, can we characterize these things? can we understand this kind
of graphs? So the first question is, we know that all graphs cannot be perfect like we
have seen that there are graphs whose chromatic number is much higher than its omega. So,
and also the definition looks a little bit cooked up because as we mentioned, if we had
just asked I want omega is equal to clique chromatic number for the entire graph it could
not have made much sense, therefore we had to introduce this extra concept that every
induced sub graph also has this property so it looks like a little cooked up but still
it so happens that there are several… graph classes graphs; in fact graph classes themselves
which are well studied graph classes which happens to be perfect graphs.
So we will see some examples. So for instance, let us look at the following: there are several
examples from the next slide, I will show, I have listed around ten classes were- which
comes under the class of perfect graphs, may be the most important among them can be bipartite
graph because that is probably the most well-known and we know it very well- bipartite graphs-
so two colorable graphs, so what do we need? we want? We will check whether it is a perfect
graph or not. We have to verify all these things are perfect graphs. So why do we say
that they are perfect graphs? that is because; so you need this property, that chromatic
number is equal to omega for every induced sub graph. Now you taken induced sub graph,
its again a bipartite graph and good thing about bipartite graphs is that if you take
an induced sub graph its again a bipartite graph.
Now we can verify whether omega is equal to chi for any bipartite graph, then it would
show that any bipartite graph is perfect. So the crucial property is that if you take
an induced sub graph of a bipartite graph its again bipartite. Therefore if you verify
that for a bipartite graph, chromatic number is equal to omega; that is enough; chromatic
number is equal to clique number; that is enough.
Now for a bipartite graph, the value of chi; so it can be of case 1. If it is 1 then it
is just a collection of isolated vertices and omega is the definitely 1, there is nothing
to worry. So let us say chi of G is equal to 2 and we know that in a bipartite graph
the biggest clique is just an edge, there is no triangle in it; there is an edge in
it, otherwise it would not be 2, chromatic number would not be 2; so the chromatic omega
equal to 2, so it is trivial bipartite graph, a trivial example, so perfect graphs.
So though it looks like it is cooked up, the entire class of a bipartite graph happen to
be perfect graphs but is not so bad, but it can capture a lot of graphs. Now let us look
at the complements of bipartite graph, it is a little one on trivial. So complements
of bipartite graph, that means, a graph whose complement is a bipartite graph, let us say
G is such a graph, can I show that chi of H is equal to omega of H for every induced
sub graph H of such a G? again we do not have to worry about every induced sub graph because
we take an induced sub graph of the complement of bipartite graph, it is again because if
you restrict our attention on that vertices on which we took the induce sub graph, the
corresponding complement will again be a bipartite, therefore it will again be a complemented
of the bipartite graphs. So induced sub graph retain the property, so we need not worry
about all the induced sub graphs, so we can just prove that if G is a complement of a
bipartite graph, then it satisfies the property that the chromatic number equal to clique
number for that; omega biggest exercise for that.
Show this thing. We should first understand what is the chromatic number of such a graph.
Now if I look at the chromatic number of this graph, what will it correspond to 4 it is
complement which happens to be a bipartite graph. See, essentially the chromatic number;
that is the number of colors required to color the vertices of the graph is the number of
independent sets to cover all the vertices of the graph, number of independent set, because
each color class corresponds to the independent set and each vertex of the graph belongs to
one of the colors classes, that is, what essentially the chromatic number is, the minimum number
of colors to color the graph, the vertices of the graph, that means the minimum number
of independent sets required; so that this collection of independent set cover all the
vertices of the graph. So the same question in the complement will
be, the minimum number of cliques complete graphs, because an independent set graph,
set here, will become a clique in the complement, an independent set will become a clique; therefore
we are asking for the minimum number of cliques to cover the entire vertex set of a bipartite
graph. This is an easy question for bipartite graph because you see in a bipartite graph
you do not even have a 3 clique, the biggest clique is only 2 edge. so what do we do?
If you want to minimize the number of cliques to cover the bipartite graph we will of case
pick up the biggest matching because we want to collect as many edges as possible, so that
they are independent, that means, they do not touch with each other, might they do not
share anything; so that will give us the matching number, if you remember alpha dash of G. So
matching number, biggest independent set, so alpha dash of G, biggest this is the…
remember alpha was the notation for independent set alpha dash corresponding edge version
of that, so alpha dash of G. Now this, but then this may not cover the
entire vertex set, because assume it may not have a perfect matching, its maximum matching
may not cover all the vertex set. So how many more we have to take now, because no more
edge can be taken; so we have to take vertices- individual singleton vertices.
So we have to take, therefore one for each remaining vertex that, n minus 2 into alpha
dash of G, this is essentially n minus alpha dash of G. How much is this, you remember
the Konig’s theorem, where we showed that alpha dash of G is essentially the vertex
cover and we see; we called it beta of G, is not it beta of G and this is essentially
alpha of G and alpha of G happens to be the omega of its complement because we are talking
about the complement graph, so the complement graphs omega. So we are talking about the
complement of a bipartite graph. In the bipartite graph its clique number will become the independent
set number, that we have seen that, in the that corresponds to the clique cover number;
that means minimum number of cliques required to cover the vertex set of the bipartite graph,
which happens to be the chromatic number of the complement of the bipartite graph. So
we got that, for the complement of the bipartite graph chi and omega are equal.
So essentially, we see that this question of whether the chromatic number for the complement
of a bipartite graph is equal to the clique number, translate to Konig’s theorem, namely
the vertex cover is equal to the matching. So though through a small translation, so
we are using it to prove this thing in the corresponding bipartite graph.
Now we go to the next one. So we have shown that bipartite graph of perfect; in fact their
complements are also perfect graphs Now here is a another one, line graphs of bipartite
graphs. So what do we mean by line graph? so we have seen the line graph many times
before, so when we study the edge- the connectivity, we have introduce the line graphs. Line graph
means, this, given a graph we are constructing another graph, where the edge set of this
given graph will be the vertex set, edge set will become will become the vertex set and
two vertices will be made adjacent there, if the corresponding edges in this original
graph are touching each other or incident with each other or coinciding on one vertex;
so this is called the line graph. Now we are saying, if you take the line graph
of bipartite line graph of a bipartite graph, that is going to be perfect. why is it perfect,
again the we do not have to worry about every possible induce sub graph because if I take
an induce graph, this essentially correspond to some edges of the bipartite, some selected
edges of the bipartite graph, so it is line graph. So again the line graph of another
graph, which is line graph of a some other bipartite; some smaller bipartite graph.
So if we prove that, for any line graph of a bipartite graph or chi is equal to omega;
that is enough as usual. So our intension would be prove now, that for line graph of a bipartite graph the chromatic number
and the independent chromatic number and clique number is equal. What is the clique number,
clique number of the line graph of a bipartite graph? of case, the clique in the line graph
should correspond to the edges incident on the same vertex because this is going to be;
if in the original graph, we have something like this, this is going to be the clique
this vertices corresponding to these edges will become the clique in the line graph,
so unless we have a triangular structure but triangles are not there in bipartite graph.
Therefore we can see that these things the; in fact which correspond to the maximum degree-
delta. So you can select the vertex of maximum degree is, delta is the maximum degree that
will correspond to the omega of the line graph of G because G being a bipartite graph.
Now we ask, if this is the omega, then what is the chi of L of G; chi of the line graph
of these things. Chi here is going to be, so the… we want to color the edge set of,
so the line graph is to be colored, that means the vertex of the line graph correspond to
an edge of the original bipartite graph. Therefore, the, coloring the vertex set in the line graph,
correspond to coloring the edge set of the bipartite graph, such that no two adjacent
edges get the same color, where, in the line graph, if you say to no two vertices which
are adjacent, get the same color, correspondingly we mean that in the original bipartite graph,
from where the line graph was constructed, we want the edges to be colored in such a
way that two adjacent edges get different color, that is essentially we are asking for
a proper edge ,coloring of the bipartite graph, again another theorem of Konig.
So we had studied earlier that, the minimum number of colors required to properly edge
color a bipartite graph is essentially delta, that is a type one graph, delta is equal to
the chi dash of G and which is essentially chi of L of G. So we have delta for chi of
L of G; delta for omega of G, so the line graph of a bipartite graph also satisfies
the condition for perfect graphs; so line graph of bipartite graph is also perfect.
Now again we look at the complements of the line graphs of bipartite graph. Are they also
perfect? as usual we can again argue that the induced sub graph; we need not worry because
induce graph themselves will be some complement of some line graph of a bipartite graph, so
we will just show that if a graph is the complement of the line graph of a bipartite graph, then
it will satisfy the chromatic number is equal to clique number, we call it. So what is the
chromatic number of the complement of the line graph of a bipartite graph?
Essentially it will be the clique cover number, as we mentioned in the last case and we studied
the complement of bipartite graph, essentially the number of colors to color the vertices
is essentially the number of independent sets to cover the vertex set. So when the when
you go back to the complement, then we took the complement of the line graph; so when
we go back to that line graph, we see that that correspond to the clique cover number,
that means the minimum number of cliques require to cover the line graph of the bipartite graph.
And now, what is the omega here, that means the clique number of the complement of the
line graph will become the biggest independent set that clique number will become, the stability
number, namely, the biggest independent set size for the line graph.
So for the line graph, if you are talking about the biggest independent set, what will
be that in the corresponding bipartite graph, because of case the vertices edges of this
graph, so in the independent set will correspond to the biggest matching that will become alpha
dash of G for the original bipartite graph. See if G is the original bipartite graph,
this will be the biggest independent set in L of G and that will be omega of L of G bar
complement, this is what this is what we are interested, so that is essentially this alpha
of L of G and that is essentially alpha dash of G, the biggest matching in the maximum
matching in the original bipartite graph. Now similarly, what is the chromatic number
of L of G bar, essentially that is the clique cover number, I can use k for that, k of L
of G -clique cover number, as we have seen each clique of the line graph of the bipartite
graph correspond to a vertex at the incident edges on a vertex, the collection of incident
edges on a vertex in the original graph. So essentially, the vertex set is essentially
the edge set of the original bipartite graph. Essentially we are seeking some vertices,
a collection of vertices from the original graph; such that every edge is incident on
one of them. So what was that, that was, we are very familiar with it, that is essentially
the vertex cover which we use to call beta of G- minimum vertex cover, so what we are
seeking. So the minimum vertex cover of the original bipartite graph will be the clique
cover number of the line graph of it and that will be the chromatic number of the compliment
of it, so this one is going to be beta of G; and this one alpha- this omega is going
to be alpha dash of G. We know there is alpha dash of G and beta dash of G are equal, again
by Konig’s theorem. So we see that if a graph is the complement of the line graph
of a bipartite graph, it has to satisfy the quality that its chromatic number is equal
to its clique number; that is what it is.
So therefore they are also perfect graphs. So we have seen bipartite graphs, their complements,
line graphs of bipartite graph, their complements. Now here is a different category the so-called
comparability graphs. So what are comparability graphs? The comparability graphs are certain
graphs defined from partial orders. So we remember what is a partial order, there is
a base set universe and then we have some relation defined on the set. So set is essentially,
it can be U and then essentially a relation is a sub set of U cross U, so is a Cartesian
product. We can draw it by directed edge, whatever the relations are, we can draw it
by direct edges like this, this can be the relation. What do we say partially, when do
we say it is a partially ordered set? we need three properties; one is this reflexivity,
that means a vertex is related to itself, a comma a, belong to R, something should be;
and the other is anti-symmetric, that means, if a b is element of R, then b a should not
be an element of R ,unless a and b are equal, so which means that if you draw this arrow
from this vertex- to- this vertex, we should not draw the reverse arrow also, that is what,
so if you are trying to represent it using a directed graph- the relation as a directed
graph. Now the third properties more important which
is namely the transitivity. Suppose a b belongs to the relation and b c belongs to the relation,
then we need a c also in the relation. So for instance if a b, we put a directed edge
here, and b c we put a directed edge, then we should have this one, a c, and also this
direction should be like this, this is what the a c should be in, this is the transitivity.
If all the three properties are satisfied it is called a partially order.
Now we can also ask the question; so suppose you are given a partially ordered set or may
we can construct a graph out of it like this directed graph of it, now we can delete the
direction from that and also we can get rid of this self looks because they do not make
much sense for us because then we are interested in simple graphs, we can anyway they are trivial,
so we get rid of those things and then we take down the underline graph- undirected
graph deleting the directions and so is… such a graph is the comparability graph corresponding
to the partial order- the comparability graph partial order.
In other words, there will be an edge between two vertices if the those corresponding elements
in the partial order are comparable. They belongs to the relation a b, will have an
edge, either a b or b a is in the relation, both cannot be one of them. So if one of them
belongs to the relation, if they are comparable, then we can of case once we define a comparability
graph of partially ordered set. So in actual question which comes is this. So there are
certain graphs which arises from a partial order, like this, if first constructed a directed
graph from the partial order, deleted the self looks, deleted the arrows, that means
directions are forgotten, then the underlying simple graph is called the comparability graph
of the partial order. Now given an undirected graph that, we can
always ask this question given some directed graph; do we have a corresponding partial
order for that? what does it mean, it is… means that, could I have got this graph from
some partial order by this procedure, sometimes it may be possible, sometimes it may not be
possible. For instance, can we think of some graph, so for instance, suppose I draw this
graph, so is it possible that I can get a some partial order, so that this is the graph
of that underlying comparability graph of that?
It is actually, we have to somehow try to recreate those arrows here, so for instance,
suppose the arrow was like this, then suppose the arrow was like this, now we are lost because
this cannot be the correct direction, because if this was, see, this is a, this is b, a
b was in the relation and b c was also in the relation, transitivity says that we should
have this also, this is not there here, this- and- this an arrow, this is not there. So
we have to be careful when we try to give the directions, this direction has to be like
this because if this is this, it has to be like this, that means then we are not bothered
a b and c b, but transitivity requirement does not trouble us now, so a b, b c, would
trouble us, but a b, c b, would not trouble us. Now here, naturally, then this has to
be directed back outward, now similarly this is to be directed inward now.
So we can add a d and also c d. a d and c d also can be directed outward and inward,
that is it. So here we could create an orientation for the arrow, such that they are transitive-
the transitivity property satisfied, of course anti-symmetric property anyway satisfied and
now if you add all these things, we would recreate the partial order like this.
So now if you add all this self looks, also and write down them as pairs, that relation
will be a partial order because here anti-symmetry reflexivity and transitivity satisfied, but
need not be always possible. For instance, sometimes we are forced to select the arrows
in such a way that finally we will end off with the contradiction. For instance, suppose
you look at the, this graph 1 2 3 4 5, this 5, now suppose I take this direction for this
arrow; naturally as I mentioned, you cannot give this direction now, because here, look
here, this look this this edge is not there if you take things, the transitivity will be broken, therefore
this is not possible. So we can only give a direction like this, now this requirement
is not there, now once you give this direction, as we know we can only give this direction,
the other way we will have this problem, again the same problem, this is not there, therefore
the transitivity will be violated. Similarly, now this has to be given this direction
and this has to be given this direction, but now here we have a problem, see this is looking
like this, this is looking like this. So now what will you do, so if you reverse it, all
the arrows will be reversed, here anyway we got into a contradiction, so if you had selected
this area, we are forced to select this arrow this arrow like this and then we are selecting
this thing, then we, this edge has to come, this edge with this direction has to come,
that is not there, so it is a contradiction. As we can see that this will happen for odd
induced cycles as long as this edge is not there, if it is and if there is an odd induced
cycle in the graph, we cannot give arrows consistently, transitive orientation, it is
called transitive orientation, is not possible. So the question now is, which are the graphs
which can be given a transitive orientation, equivalent to asking that, which are the class
of graphs- undirected graphs which could have come from some partial order, which could
have in the become the comparability graph of some partial, we will just say that the
class of graphs -undirected graphs, which can be transitively oriented, that means ,which
can be seen as the comparability graph of some partial order is the comparability graph,
this class of graphs called comparability graphs.
Now our question is, are comparability graphs perfect? so as we can see, if you are given
a comparability graph and if you consider its induced sub graph, if you are given a
comparability graph and if you consider its induced sub graph, naturally they are also
comparability graph, why because if you can transitively will orient the entire graph,
the same transitive orientation will work for an induced sub graph also, if a graph
is comparability graph and induced sub graph of it is also comparability graph, therefore
we do not have to worry the complicated condition about the induced sub graph, we just have
to show that, any comparability graph, the property that chi is equal to omega, that
means the chromatic number is equal to clique number is valid, that is all we have to verify
to prove that comparability graphs are perfect. Now let us see what does it may, what is chi
here, what is chi of chi of G here and what is omega of G here. As we can see omega of
G is the biggest clique number, so the biggest clique size, so essentially, now we just have
to show that, see we know that omega of G is less than equal to chi of G. Now if you
show a coloring which uses only omega of G number of colors, then it means that omega
of G equal to chi of G, so that is what we are going to do now, we will show a coloring
such that the number of colors used is only omega of G.
Now, we should also understand what is this omega of G in a comparability graph, it is
the maximum clique but any clique, because it is transitively oriented on that. If we
look at the directions given to the edges inside the clique, they would not form any
cycles- directed cycles because it is transitively oriented. It is not possible to have, so naturally
it should be acyclic and so they should be an ordering of the vertices, then it corresponds
to a total ordering; in fact within the partial order, so we get a subset which is totally
ordered with respect to that relation, any two if you take there is a direction between
the arrows, between there is an edge and there is a direction between them.
So naturally we can do it apological sort on there, then we get from the lowest to the
highest in that, that is the total order there. So we say that such totally ordered sub sets
of a partially ordered set, he said as, it is a chain of the partial order, we have seen
at when we studied the Dilworth’s theorem long time ago and we studied the Gallai-Milgram
theorem, we have seen how Dilworth’s theorem about partial ordered sets follows from the
Gallai-Milgram theorem, so we know what is chain, what is anti-chain.
So chain, essentially the chain of a partial order correspond to the clique, essentially
the clique of the comparability graph, correspond to the corresponding partial order a chain
in the corresponding partial order and similarly a chain in the partial order will become a
clique in the comparability graph. It is very obvious because chain means everything is
related with each other, every pair is related, which related, is part of the relation therefore
those edges will be there, so that will become a clique.
Now, so we can consider this coloring, here is a way to color now, so for every vertex
we have seen it in the Gallai Roy theorem also this technique, so what we do is, we
can we can take a vertex and you can look at the, say Gallai Roy theorem, so we can
look at the biggest chain that is starting from there, I mean the… among the chain
which are starting here and going from, you can look at the, which is the biggest chain,
the number of vertices in that can be given as the color of this, this color, this within
the number of vertices in the biggest chain now everything gets.
So of course now we are going to claim that this the proper coloring, if this is the proper
coloring we are done because we have only used with the biggest color, we have used
only correspond to- or less than equal to the biggest length of a chain in this graph
and the biggest length of a chain is only the clique number, so it is going to be less
than equal to clique number, it cannot less than clique number, if it is the proper coloring,
because we know that clique number is going to low bound for the chromatic number, so
it can only be greater than or equal to. So if we went somehow demonstrate that this is
indeed a valid proper coloring, then the number of colors used will be less than equal to
the biggest chain; that is the clique number, so it has be equal to the clique number that
is the biggest chain. So is it a proper coloring, suppose not then
be, should an edge where some edge like this, say, some edge like this, where, so the edge,
if the edge direction can be like this, so that means this also got the same color, this
also got the same color that is why our contradiction is. Now why did this get the same color as
this? here this was the biggest chain starting from here here definitely there is a chain
staring with green edge and then following this, this is one more than this, he should
have got a bigger number, so that is a contradiction and of course if the direction was the other
way, suppose the direction was like this, then we would follow, we would consider the
biggest chain starting from this and this the length of this will be the color of this
person and this person’s color will be one more than this, at least they cannot be equal
therefore we see that it is proper coloring and it follows that, since we have only used
the length of the maximum chain is the biggest color here, so the chromatic number is going
to be less than equal to the omega but it cannot be strictly less, so it has to be equal,
so that is what. So we what we have now shown is, any comparability
graph also satisfy the property that chromatic number is equal to omega and because the induced
sub graphs are indeed, again comparability graphs, we get that the comparability graphs
are perfect.
The next one is co comparability graph, namely the complements of comparability graphs. So
every time we are considering a class, we are also considering its complement because
this will become useful later, because we every time; we see that for a class, when
see, there it is perfect, its complement is also happening to be a perfect, the complement
is also perfect, so there should be a reason for this thing, we will explore it later.
So there is a general reason for this thing, so later when we prove the general theorems,
all these will become, will get connected in one general statement.
So what about co comparability graphs. The co comparability graphs means essentially
the complements of this thing, so again we ask what is chi there, so I will say chi of
omega of G bar, what is that is omega of G bar is alpha of G- the independent set number,
this is, the essentially, the clique cover number of G, so we can just ask what does
it mean, so alpha of G in the comparability graph, essentially the independent set, so
the pair wise non-comparable elements there, what we have seen it before, that is called
anti-chain in the partial order terminology, it is known, it is essentially independent
set, that is all, but we use to call it anti-chain when we studied Dilworth’s theorem, we had
called it biggest anti-chain- maximum anti-chain. Now, this one, each clique being a chain the
collection of cliques, which cover the entire vertices, that is a chain cover in the terminology
of the partial orders chain cover, we are the minimum number of chains to cover the
elements of the partial order, this is exactly what Dilworth’s theorem considered. The
minimum number of chains to cover the elements of the partial order and the biggest anti-chain
Dilworth’s theorem had told that these two things are equal, essentially, therefore these
two things are equal chi of G bar is equal to omega of G bar.
So, we are back to the Dilworth’s theorem. When it when it consider the complement of
the comparability graphs, their chi and omega correspond to the two parameters, which Dilworth’s
theorem told as are equal, so complements of comparability graphs are also perfect.
And now the next one we will look at, very well-known class of graphs called interval
graphs. Interval graphs are very well known and also useful in many practical situations
and essentially they are defined like this, so to define an interval graph, so we need
the real line.
Now an interval in the real line, so we take closed interval for convenience, so can be
marked like this, now suppose I have several intervals- a family of intervals, in the real
line, I just take several color for this thing, these are several intervals like this, may
be there is other one here. Now we see that we can get a graph out of
edge in the following way: now I am putting these vertices, here yellow and now here green,
so these are essentially, corresponding to the red interval I put a red vertex, corresponding
to the green interval I put a green vertex, corresponding to the yellow interval I put
a yellow vertex. Now I connect the vertices together in using
the following rule: if two intervals intersect, for instance, here for yellow and red are
intersecting, therefore I will put a connection between them, and, green and red are intersecting,
green and blue are intersecting, green and this dark green are intersecting, and then
this yellow and red are intersecting, yellow and blue are intersecting, and this- and-
this are intersecting but this yellow and this are not intersecting, if I not this is
an interval, no of course this yellow and green is also intersecting, this is the interval
graph, this is the interval graph corresponding to the family of intervals here.
So essentially, we say that this is the intersection graph of this family of intervals, which I
have drawn here, how do I mean by intersection graphs? so you can, so it is a more general
concept, then interval graphs essentially you can have a universe and let us say these
are some subsets S 1, S 2, S 3, S 4 etcetera, which I have selected from the universe, so
you write some subset of S i is a subset of U, that is all.
Now we can ask, S 1 and S 2 do they have any element in common sub, is there the element
here and here, some S here and some here in common element, in that case, see I will introduce
a vertex corresponding to each of this subsets and then if there is an intersection between
S 1 and S 2, I will put an edge if there is no intersection, if they are disjoint, then
I would not put an edge, for instance, S 1, if S 1 intersection S 3 equal to phi, then
there would not be any edge here, this edge only, but on the other hand if S 1 intersection
S 4 happens to be nonempty, then we will put an edge here, so the graph resulting from
such intersection pattern is called the intersection graph of this family S 1, S 2, S 3 etcetera-
family of subsets U.
So here in the case of interval graph, here U is the real line, the universe is the real
line itself and the subsets S 1, S 2, S 3 etcetera, this intervals they are subsets
of points and now whenever there is an intersection between them we are putting an edge between
the corresponding vertices that is all. So therefore we can say that the interval
graph are the intersection graphs of some family of intervals on the real line, so now,
see we can always, like in the case of comparability graph we have defined interval graph using
a set of a family of intervals on the interval.
Now it is possible that you have given a graph first- an undirected graph, first you can
ask, is it an interval graph? What is it mean, it means that, can we draw a collection of
intervals corresponding to the vertex set of the graphs? we can say that for this vertex,
this is the interval; this vertex, this is the interval, like that we can, we get a mapping
between the vertex set of the G and to some family of intervals on the real lines, such
that G happens to be the intersection graph of that family of interval graphs, is it possible
to construct such a family of intervals corresponding to G? This is what we ask when we ask whether
G is an interval graph. If it can be constructed, then we say the
G is an interval graph, otherwise G is not an interval graph. So it is a very natural
thing to ask, are their graphs which are not interval graphs or is it possible that for
every graph we can get an interval representation, of course every graph we cannot get an interval
representation, quickly we can see whether this graph… so this is a four cycle, can
it get an interval representation? So for instance, this vertex, suppose, it has an
interval, so I mark it with red green and then violet.
So this red, suppose I give this interval, so arbitrarily to give this interval, then
that blue, I give intuitive argument, suppose blue I give, an interval it has to intersect
with it, suppose like this, now it, you can draw it in this direction or this direction,
can it draw it completely inside red? no because then orally input violet because if I draw
this yellow completely inside red, then what will, when I put violet, violet will have
to touch yellow but then it will automatically touch red also, which is not allowed because
there is no edge here, so the yellow has to come out of the red, so it is essentially it should be either like
this or either like this, some other, so will without, let us say like this.
Now once, I have to draw violet without touching red, so touching red like that, we cannot
put violet totally inside yellow, as we mentioned before, so we cannot draw violet to this direction,
violet will have to be drawn in this direction now.
Now we have stuck for green, what will happen to the green, because a green, it has to touch
violet, it has to touch red but it should not touch yellow, is it possible to draw like
that, of course a little non-trigger as argument, so, but you can see that it is not possible,
so, but I will encourage the students to come up with the very rigorous statement- argument
for this thing, but, see you, this graph cannot be converted to a family of interval graph,
such that this becomes the intersection graph of that, therefore you see there are graphs
which are not interval graphs, so the class of graphs- undirected graphs, such that we
can map the vertices of it to the intervals on the real line, such that this becomes the
intersection graph of those family of, that family of intervals is called an interval
graph. Now we will, the… our intension now is to
see whether interval graphs are perfect graphs or not. So the, to see whether interval graphs are perfect graphs
or not, we again have to see whether chi of G, what is chi of G, what is omega of G here.
Now you see again, like in all the previous cases we discussed, we do not have to worry
about all the induce sub graph because the induce sub graph themselves will be interval
graphs because the vertices will correspond to some interval, they delete the other intervals,
we still get an intersection pattern for that, therefore induce sub graph of an interval
graph is again an interval graph, so we just have to show that chi of G is equal to omega
of G, if G is an interval graph and that will show that they are perfect graphs. Now is
it true, what is omega of G- it is clique. Now when you say that clique, how will they
look in interval representation, so each vertex corresponding to the clique has an interval
and they pair wise intersect.
Now in a collection of intervals, if any pair has an intersection, then we can say that
there is a common intersection also, this is called the Helly property or the interval
graphs. So we can try it like, so for instance, suppose here, there is an interval, there
is another interval here, there is another interval here, so there is an another interval
here, now the, what my condition is, every pair of intervals should intersect, now can
you see that there is going to be a common intersection point, it is not very difficult
because among this, so I scan from these, so for instance, I can see that any two of
them if you take this intersection point of the two.
Now the third one cannot start, we cannot have interval like this because if I put an
interval like this, then, because these are, this intervals ends here, so this will not
cut way this, so it has to start before this, and, but then, can it end? For instance, this
any interval, can it end before this point, in that case it would not cut it, so everything
will have to go in to this. So we will get a common intersection for all
the three of them and then we can refine this argument to say that there should be a common
intersection part for all the intervals we take part in the clique, so there will be
a common intersection part and a point from this common intersection part is such that
they belong to all the intervals, which take part in the clique, so that can be taken as
a point, which represent the clique, that means any clique correspond, to some point
we can associate some point to a given clique in the interval graph why because property
of this point will be there this point, belongs to all the intervals corresponding to the
vertices clique. So essentially, that is the nature of this
omega in the interval graphs. Now we have to understand what is the nature of chi and
then we have to show that both of them are equal, that we will do in the next class,
so our intension here is to study several such classes and then show that, see, this
perfect graphs though the definition happens to be a little centroid, a little cooked up,
but it is not like that, several important special class of graph falls in this category,
so that we will do in the next class. Thank you.