Discrete Math Seminar: Ararat Harutyunyan

Abstract:

Given a graph G, the vertex-arboricity of G, denoted by a(G), is the smallest integer k such that V(G) can be partitioned into k sets each of which induces an acyclic subgraph. This notion relates to the chromatic number of a graph, and was considered as one of the methods of attack on the Four Color theorem. We will present a survey of results and conjectures in the area, focusing on planar graphs. The talk will finish with the presentation of some new results obtained by the speaker (jointly with B. Mohar).