Premium
Largest bipartite subgraphs in triangle‐free graphs with maximum degree three
Author(s) -
Bondy J. A.,
Locke S. C.
Publication year - 1986
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.3190100407
Subject(s) - combinatorics , mathematics , bipartite graph , complete bipartite graph , discrete mathematics , degree (music) , induced subgraph , graph , cograph , line graph , 1 planar graph , vertex (graph theory) , physics , acoustics
Abstract Let G be a triangle‐free, loopless graph with maximum degree three. We display a polynomial algorithm which returns a bipartite subgraph of G containing at least ⅘ of the edges of G. Furthermore, we characterize the dodecahedron and the Petersen graph as the only 3‐regular, triangle‐free, loopless, connected graphs for which no bipartite subgraph has more than this proportion.