The biparticity of a graph
- 1 June 1977
- journal article
- research article
- Published by Wiley in Journal of Graph Theory
- Vol. 1 (2) , 131-133
- https://doi.org/10.1002/jgt.3190010208
Abstract
The biparticity β(G) of a graph G is the minimum number of bipartite graphs required to cover G. It is proved that for any graph G, β(G) = {log2χ(G)}. In view of the recent announcement of the Four Color Theorem, it follows that the biparticity of every planar graph is 2.Keywords
This publication has 5 references indexed in Scilit:
- Every planar map is four colorableBulletin of the American Mathematical Society, 1976
- k-Components, Clusters and Slicings in GraphsSIAM Journal on Applied Mathematics, 1972
- COVERING AND PACKING IN GRAPHS, I.Annals of the New York Academy of Sciences, 1970
- GRAPH THEORYPublished by Defense Technical Information Center (DTIC) ,1969
- On Partitioning Planar GraphsCanadian Mathematical Bulletin, 1968