Graphs are mathematical structures used to model pairwise relations between objects. There are many applications of graphs in various areas, such as computer science, sociology, biology, etc.

In this talk, among many concepts in graph theory, we discuss about graph decomposition which deals with a partition of large/dense graphs into small/sparse graphs. We introduce several graph decomposition problems, related puzzles and its applications.

Recently, Kuhn, Osthus, Tyomkyn and the speaker developed a new method for approximate decomposition of dense graphs into sparse graphs. We briefly introduce this method and its application to famous decomposition problems.