Affordable Access

Publisher Website

Triangle-free subcubic graphs with minimum bipartite density

Authors
Journal
Journal of Combinatorial Theory Series B
0095-8956
Publisher
Elsevier
Publication Date
Volume
98
Issue
3
Identifiers
DOI: 10.1016/j.jctb.2007.09.001
Keywords
  • Triangle-Free
  • Subcubic
  • Bipartite Subgraph
  • Bipartite Density
Disciplines
  • Computer Science

Abstract

Abstract A graph is subcubic if its maximum degree is at most 3. The bipartite density of a graph G is max { ε ( H ) / ε ( G ) : H is a bipartite subgraph of G}, where ε ( H ) and ε ( G ) denote the numbers of edges in H and G, respectively. It is an NP-hard problem to determine the bipartite density of any given triangle-free cubic graph. Bondy and Locke gave a polynomial time algorithm which, given a triangle-free subcubic graph G, finds a bipartite subgraph of G with at least 4 5 ε ( G ) edges; and showed that the Petersen graph and the dodecahedron are the only triangle-free cubic graphs with bipartite density 4 5 . Bondy and Locke further conjectured that there are precisely seven triangle-free subcubic graphs with bipartite density 4 5 . We prove this conjecture of Bondy and Locke. Our result will be used in a forthcoming paper to solve a problem of Bollobás and Scott related to judicious partitions.

There are no comments yet on this publication. Be the first to share your thoughts.