Premium
On the bipartite density of regular graphs with large girth
Author(s) -
Zýka Ondřej
Publication year - 1990
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.3190140602
Subject(s) - combinatorics , mathematics , bipartite graph , triangle free graph , girth (graph theory) , graph , complete bipartite graph , discrete mathematics , foster graph , odd graph , edge transitive graph , graph power , line graph , 1 planar graph
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.