𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Bipartite Subgraphs of Graphs with Maximum Degree Three

✍ Scribed by Stanisław Bylka; Adam Idzik; Jan Komar

Publisher
Springer Japan
Year
1999
Tongue
English
Weight
108 KB
Volume
15
Category
Article
ISSN
0911-0119

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

Largest bipartite subgraphs in triangle-
Largest bipartite subgraphs in triangle-free graphs with maximum degree three
✍ J. A. Bondy; S. C. Locke 📂 Article 📅 1986 🏛 John Wiley and Sons 🌐 English ⚖ 977 KB

Let G be a triangle-free, loopless graph with maximum degree three. We display a polynomi$ algorithm which returns a bipartite subgraph of G containing at least 5 of the edges of G. Furthermore, we characterize the dodecahedron and the Petersen graph as the only 3-regular, triangle-free, loopless, c

Bipartite labeling of trees with maximum
Bipartite labeling of trees with maximum degree three
✍ Bonnington, C. Paul; ?ir�?, Jozef 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 258 KB 👁 3 views

Let T = (V, E) be a tree with a properly 2-colored vertex set. A bipartite labeling of T is a bijection ϕ: V → {1, . . . , |V |} for which there exists a k such that whenever ϕ(u) ≤ k < ϕ(v), then u and v have different colors. The α-size α(T ) of the tree T is the maximum number of elements in the

Sizes of graphs with induced subgraphs o
Sizes of graphs with induced subgraphs of large maximum degree
✍ Paul Erdős; Talmage James Reid; Richard Schelp; William Staton 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 249 KB

Graphs with n + k vertices in which every set of n +j vertices induce a subgraph of maximum degree at least n are considered. For j = 1 and for k fairly small compared to n, we determine the minimum number of edges in such graphs.

Constructing a bipartite graph of maximu
Constructing a bipartite graph of maximum connectivity with prescribed degrees
✍ Asano, Takao 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 328 KB 👁 3 views

d 2,n 2 ) is a bipartite graphical sequence, if there is a bipartite graph G with degrees {D 1 , D 2 } (i.e., G has two independent vertex sets In other words, {D 1 , D 2 } is a bipartite graphical sequence if and only if there is an n 1 1 n 2 matrix of 0's and 1's having d 1j 1 1's in row j 1 and