Geodesic
A result on large induced subgraphs with prescribed residues in bipartite graphs
Zachary Hunter1
1Oxford University
The electronic journal of combinatorics, Tome 30 (2023) no. 1
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

It was proved by Scott that for every $k\ge 2$, there exists a constant $c(k)>0$ such that for every bipartite $n$-vertex graph $G$ without isolated vertices, there exists an induced subgraph $H$ of order at least $c(k)n$ such that $\operatorname{deg}_H(v) \equiv 1\pmod{k}$ for each $v \in H$. Scott conjectured that $c(k) = \Omega(1/k)$, which would be tight up to the multiplicative constant. We confirm this conjecture.
DOI : 10.37236/11454
Classification : 05C07, 05C35, 05C81
Mots-clés : Scott's conjecture

Zachary Hunter  1

1 Oxford University 
@article{10_37236_11454,
     author = {Zachary Hunter},
     title = {A result on large induced subgraphs with prescribed residues in bipartite graphs},
     journal = {The electronic journal of combinatorics},
     year = {2023},
     volume = {30},
     number = {1},
     doi = {10.37236/11454},
     zbl = {1507.05022},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/11454/}
}
TY  - JOUR
AU  - Zachary Hunter
TI  - A result on large induced subgraphs with prescribed residues in bipartite graphs
JO  - The electronic journal of combinatorics
PY  - 2023
VL  - 30
IS  - 1
UR  - http://geodesic.mathdoc.fr/articles/10.37236/11454/
DO  - 10.37236/11454
ID  - 10_37236_11454
ER  - 
%0 Journal Article
%A Zachary Hunter
%T A result on large induced subgraphs with prescribed residues in bipartite graphs
%J The electronic journal of combinatorics
%D 2023
%V 30
%N 1
%U http://geodesic.mathdoc.fr/articles/10.37236/11454/
%R 10.37236/11454
%F 10_37236_11454
Zachary Hunter. A result on large induced subgraphs with prescribed residues in bipartite graphs. The electronic journal of combinatorics, Tome 30 (2023) no. 1. doi: 10.37236/11454

Cité par Sources :