A note on bipartite subgraphs of triangle-free graphs

Autor:	James B. Shearer
Rok vydání:	1992
Předmět:	Vertex (graph theory) Discrete mathematics Combinatorics Corollary Applied Mathematics General Mathematics Bipartite graph Computer Graphics and Computer-Aided Design Complete bipartite graph Software Graph Mathematics
Zdroj:	Random Structures & Algorithms. 3:223-226
ISSN:	1042-9832
DOI:	10.1002/rsa.3240030211
Popis:	Let G be a triangle‐free graph on n points with m edges and vertex degrees d1, d2,…, dn. Let k be the maximum number of edges in a bipartite subgraph of G. In this note we show that k ⩾ m/2 + Σ **image** √di. It follows as a corollary that k ⩾ m/2 + cm3/4. © 1992 Wiley Periodicals, Inc.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::d9a264badc05d548e4b5470ba40e266b https://doi.org/10.1002/rsa.3240030211 Zobrazit plný text záznamu Plný text