𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On the bipartite density of regular graphs with large girth

✍ Scribed by Ondřej Zýka

Publisher
John Wiley and Sons
Year
1990
Tongue
English
Weight
154 KB
Volume
14
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

Let B(G) be the edge set of a bipartite subgraph of a graph G with the maximum number of edges. Let b~k~ = inf{|B(G)|/|E(G)‖G is a cubic graph with girth at least k}. We will prove that lim~k → ∞~ b~k~ ≥ 6/7.

📜 SIMILAR VOLUMES

A lower bound on the order of regular gr
A lower bound on the order of regular graphs with given girth pair
✍ C. Balbuena; T. Jiang; Y. Lin; X. Marcote; M. Miller 📂 Article 📅 2007 🏛 John Wiley and Sons 🌐 English ⚖ 129 KB 👁 1 views

## Abstract The girth pair of a graph gives the length of a shortest odd and a shortest even cycle. The existence of regular graphs with given degree and girth pair was proved by Harary and Kovács [Regular graphs with given girth pair, J Graph Theory 7 (1983), 209–218]. A (δ, __g__)‐cage is a small

The maximum valency of regular graphs wi
The maximum valency of regular graphs with given order and odd girth
✍ Guo-Hui Zhang 📂 Article 📅 1992 🏛 John Wiley and Sons 🌐 English ⚖ 294 KB 👁 1 views

## Abstract The odd girth of a graph __G__ is the length of a shortest odd cycle in __G__. Let __d__(__n, g__) denote the largest __k__ such that there exists a __k__‐regular graph of order __n__ and odd girth __g__. It is shown that __d____n, g__ ≥ 2|__n__/__g__≥ if __n__ ≥ 2__g__. As a consequenc

The circular chromatic number of series-
The circular chromatic number of series-parallel graphs with large girth
✍ Chien, Chihyun; Zhu, Xuding 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 213 KB 👁 2 views

It was proved by Hell and Zhu that, if G is a series-parallel graph of girth at least 2 (3k -1)/2 , then χ c (G) ≤ 4k/(2k -1). In this article, we prove that the girth requirement is sharp, i.e., for any k ≥ 2, there is a series-parallel graph G of girth 2 (3k -1)/2 -1 such that χ c (G) > 4k/(2k -1)

The chromaticity of complete bipartite g
The chromaticity of complete bipartite graphs with at most one edge deleted
✍ C. P. Teo; K. M. Koh 📂 Article 📅 1990 🏛 John Wiley and Sons 🌐 English ⚖ 364 KB 👁 1 views

## Abstract Let __K(p, q), p ≤ q__, denote the complete bipartite graph in which the two partite sets consist of __p__ and __q__ vertices, respectively. In this paper, we prove that (1) the graph __K(p, q)__ is chromatically unique if __p__ ≥ 2; and (2) the graph __K(p, q)__ ‐ __e__ obtained by del

On the Density of Subgraphs in a Graph w
On the Density of Subgraphs in a Graph with Bounded Independence Number
✍ Pavel Valtr 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 260 KB

Let \_(n, m, k) be the largest number \_ # [0, 1] such that any graph on n vertices with independence number at most m has a subgraph on k vertices with at lest \_ } ( k 2 ) edges. Up to a constant multiplicative factor, we determine \_(n, m, k) for all n, m, k. For log n m=k n, our result gives \_(