Feeds:
Posts

## Archive for the ‘Uncategorized’ Category

During a conference at our institute in honor of Prof. C R Rao’s 90th birthday celebrations,  Prof. K R Parthasarathy asked me if I had read the proof of four colour theorem (4CT). I said I know the idea behind it and the general outline. He told me that that is not enough.  A good part of graph theory was developed due to 4CT, it is essential that one understands its proof. He says that is how one can build the necessary muscle power. Who am I to say no? So I start out the mammoth task of trying to understand the proof of 4CT.  I am keeping 3 months for the same and if  it does not go well, I plan to try to prove it from the scratch :).

There are some interesting problems that I happen to come across during the conference, which I will post here soon.

## Do three longest paths share a vertex?

One of the reasons I find graph theory so interesting is that one can ask so basic and fundamental questions that are extremely difficult to answer.  Here is one such problem.

It is easy to see that any pair of maximum length paths in a connected graph should share a vertex. Otherwise, we can get a longer path contradicting the maximality.  The natural question that arises is what can we say about three longest paths? What about $k$ maximal paths? Do all of them share a vertex?

Zamfirescu and Skupien  show that for $k \ge 7$ this need not be the case.

Balister, Gyori, Lehel and Schelp show that for interval graphs and circular arc graphs, all paths do have non-empty intersection.

Recently, Maria Axenovich  shows that any 3 longest paths in outerplanar graphs have a common vertex.

It would be interesting to look at planar graphs now that outerplanar graphs are known.

Hi, I am $Narayanan$. I plan to write about open problems in graph theory and related topics that I happen to come across.