✦ LIBER ✦

The biparticity of a graph

✍ Scribed by Frank Harary; Derbiau Hsu; Zevi Miller

Publisher: John Wiley and Sons
Year: 1977
Tongue: English
Weight: 116 KB
Volume: 1
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.3190010208

No coin nor oath required. For personal study only.

✦ Synopsis

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) = {log~2~χ(G)}. In view of the recent announcement of the Four Color Theorem, it follows that the biparticity of every planar graph is 2.

📜 SIMILAR VOLUMES

On the hamiltonian path graph of a graph

✍ George R. T. Hendry 📂 Article 📅 1987 🏛 John Wiley and Sons 🌐 English ⚖ 491 KB 👁 1 views

The hamiltonian path graph H(F) of a graph F is that graph having the same vertex set as F and in which two vertices u and u are adjacent if and only if F contains a hamiltonian u -u path. First, in response to a conjecture of Chartrand, Kapoor and Nordhaus, a characterization of nonhamiltonian grap

Traversability and connectivity of the m

Traversability and connectivity of the middle graph of a graph

✍ Takashi Hamada; Izumi Yoshimura 📂 Article 📅 1976 🏛 Elsevier Science 🌐 English ⚖ 871 KB

The core of a graph

✍ Pavol Hell; Jaroslav Nešetřil 📂 Article 📅 1992 🏛 Elsevier Science 🌐 English ⚖ 924 KB

The asymptotic probability that a random

The asymptotic probability that a random graph is a unit interval graph, indifference graph, or proper interval graph

✍ Joel E. Cohen 📂 Article 📅 1982 🏛 Elsevier Science 🌐 English ⚖ 431 KB

A note on the exceptional graph of the c

A note on the exceptional graph of the cubic lattice graph characterization

✍ Curtis R Cook 📂 Article 📅 1973 🏛 Elsevier Science 🌐 English ⚖ 253 KB

The A4-structure of a graph

✍ Michael D. Barrus; Douglas B. West 📂 Article 📅 2011 🏛 John Wiley and Sons 🌐 English ⚖ 215 KB