Dear Mr Bibek Bhattarai, my colleague Raycho Mukelov (https://www.researchgate.net/profile/Raycho_Mukelov) deals with problems in Graph Theory

He looks for Graph Theory applications in different areas.

Dear Bibek Bhattarai,

Nowadays, processing of large graphs is a very important problem in graph applications. People have been working on graph processing frameworks for GPUs, data centres, etc. as well as developing new graph algorithms suitable for these platforms. For example, in this paper I talk about detecting cycles in large graphs using a distributed algorithm:

https://www.researchgate.net/publication/283642998_Distributed_cycle_detection_in_large-scale_sparse_graphs

There are also several interesting open problems in Graph Theory in general:

Erdős–Hajnal conjecture

Tuza's conjecture

In this website, for example, there is a list of open problems:

http://www.openproblemgarden.org/category/graph_theory

Conference Paper Distributed cycle detection in large-scale sparse graphs

Many Real world problems can be modeled as graph. But uncertainty exists in those real world problem. So,  the main challenge is how to handle those uncertainties in graph theory problem  

Topological structure of graphs (networks) are of significant importance when dealing with complex networks (especially complex computer networks). The description of the topological structure of complex networks and techniques of their construction as well as their effective enumeration are both extremely relevant and sometimes very challenging problems to solve. In this direction, the understanding of the general behavior of complex networks will allow solving fundamental problems in several branches of theoretical and applied sciences such as Physics, Chemistry, Biology, Medicine, Ecology, Computer Science, and Engineering.