On the complete bipartite decomposition of planar graphs

Abstract

Given a graph G, a complete bipartite decomposition of G is a partition π of E(G) into disjoint sets E(H_i) such that each subgraph H_i induced by E(H_i) is an edge-disjoint union of complete bipartite subgraphs of G. G's complete bipartite capacity c(G) is the minimum cardinality of π over all of complete bipartite decompositions, and its complete bipartite valency θ(G) is the minimum, over all complete bipartite decompositions π, of the maximum number of elements in π incident with a vertex. A star decomposition, the star capacity (or conventionally, star arboricity) st(G) and the star valency θ_s(G) of a graph G are defined analogously. In this article, we establish the sharp upper bounds on θ(G), c(G), st(G) and θ_s(G) for outerplanar graphs and on θ(G), θ_s(G) and c(G) for planar graphs. We also find the characteristic of graphs with small value of θ_s(G) and furthermore the classification of planar graphs in terms of θ_s(G).