Face 2-colorable quadrilateral embeddings of complete bipartite graphs

Hung-Lin Fu*, I. Fan Sun

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

Abstract

An embedding is said to be face 2-colorable if the faces of the embedding can be colored with two colors such that no two monochromatic faces share an edge. In this paper, it is proved that a face 2-colorable quadrilateral embedding of the complete bipartite graph Km,n exists if and only if m and n are even. Moreover, we obtain a different proof of γ(Km,n) = [ (m-2)(n-2)/4] which does not use rotational scheme and the methods known.

Original languageEnglish
Pages (from-to)117-129
Number of pages13
JournalUtilitas Mathematica
Volume62
StatePublished - 1 Nov 2002

Fingerprint Dive into the research topics of 'Face 2-colorable quadrilateral embeddings of complete bipartite graphs'. Together they form a unique fingerprint.

Cite this