Back to Search
Start Over
On the minimal degree condition of graphs implying equality of the largest Kr-free subgraphs and (r − 1)-partite subgraphs.
- Source :
-
Discrete Mathematics . Aug2021, Vol. 344 Issue 8, pN.PAG-N.PAG. 1p. - Publication Year :
- 2021
-
Abstract
- Erdős posed the problem of finding conditions on a graph G which imply that the largest number of edges in a triangle-free subgraph is equal to the largest number of edges in a bipartite subgraph. We consider a more general problem by defining δ r to be the least number so that any graph G on n vertices with minimum degree δ r n has the property that the largest number of edges in an (r − 1) -partite subgraph equals to the largest number of edges in a K r -free subgraph. We show that 3 r − 4 3 r − 1 < δ r ≤ 4 (3 r − 7) (r − 1) + 1 4 (r − 2) (3 r − 4) when r ≥ 4. We also show δ 4 ≤ 0.9415. [ABSTRACT FROM AUTHOR]
- Subjects :
- *SUBGRAPHS
*EDGES (Geometry)
*BIPARTITE graphs
*MAXIMA & minima
Subjects
Details
- Language :
- English
- ISSN :
- 0012365X
- Volume :
- 344
- Issue :
- 8
- Database :
- Academic Search Index
- Journal :
- Discrete Mathematics
- Publication Type :
- Academic Journal
- Accession number :
- 150614400
- Full Text :
- https://doi.org/10.1016/j.disc.2021.112453