Niederlassungs- und Aufenthaltsbewilligung, hat sich ergeben: A.-A.S._, geboren 1959, ist Staatsangehöriger von Pakistan. Er reiste 1986 in die Schweiz ein und stellte ein Asylgesuch, welches der Delegierte für das Flüchtlingswesen mit Verfügung vom 13. Januar 1987 ablehnte. Das Eidgenössische Justiz- und Polizeidepartement wies die gegen diese Verfügung erhobene Beschwerde am 28. Oktober 1988 ab, unter Ansetzung einer Frist zum Verlassen der Schweiz bis 28. Februar 1989. Nach dem Beschwerdeentscheid im Asylverfahren und noch vor Ablauf der angesetzten Ausreisefrist, am 21. Dezember 1988, heiratete A.S._ eine um 14 Jahre ältere Schweizer Bürgerin, X._. Gestützt auf diese Heirat erhielt er eine Aufenthaltsbewilligung, und 1993 entsprach das Amt für Polizeiweisen (Fremdenpolizei) des Kantons Graubünden seinem Gesuch um Erteilung der Niederlassungsbewilligung. Im Oktober und November 1994 wurden der Fremdenpolizei des Kantons Graubünden Informationen (zwei Schreiben in englischer Sprache) unter anderem des Inhalts zugespielt, dass die Ehe A.S._-X. _ nicht gelebt werde und vielmehr vorgetäuscht sei. A.S._ sei mit einer Pakistanerin verheiratet. Eine diesbezügliche Erkundigung bei der Schweizer Botschaft in Pakistan (anfangs 1995) verlief ergebnislos. Nachdem die Eheleute spätestens seit Ende 1991 getrennt gelebt hatten, leitete X._ am 13. Juni 1994 das Scheidungsverfahren ein. Ihre Ehe mit A.S._ wurde am 15. Dezember 1994 geschieden. Mit Verfügung vom 7. Mai 1996 stellte die Staatsanwaltschaft des Kantons Graubünden eine gegen A.S._ eröffnete Strafuntersuchung wegen Erschleichung einer Falschbeurkundung und mehrfacher Ehe ein. Im August 1996 stellte A.S._ das Gesuch um Familiennachzug für B.S._, die er gemäss pakistanischen Zivilstandsregisterauszügen am 12. Januar 1996 in Pakistan geheiratet hatte. Die Ehefrau erhielt in der Folge eine Jahresaufenthaltsbewilligung. B.-Im Juni 1997 ging bei der Fremdenpolizei des Kantons Graubünden erneut ein anonymer Brief eines Y._ ein, in welchem behauptet wurde, dass A.S._ das Heiratsdatum in der pakistanischen Ehestandsregisterurkunde habe fälschen lassen. Gemäss darauf bei der Schweizer Botschaft in Pakistan veranlassten Nachforschungen (case note einer Vertrauensperson vom 22. Oktober 1997) soll die Ehe bereits im Jahr 1992 geschlossen worden sein. Am 16. November 1998 widerrief die Fremdenpolizei die Niederlassungsbewilligung von A.S._ und lehnte ein Gesuch um Verlängerung der Aufenthaltsbewilligung seiner Ehefrau ab. Zugleich setzte sie dem Ehepaar eine Ausreisefrist an. Das Justiz-, Polizei- und Sanitätsdepartement des Kantons Graubünden wies die gegen die Verfügung der Fremdenpolizei erhobene Beschwerde am 19. April 1999 ab. Mit Urteil vom 6. Juli 1999 wies das Verwaltungsgericht des Kantons Graubünden den gegen diesen Beschwerdeentscheid erhobenen Rekurs ab und setzte den Eheleuten S._ eine Frist von vier Monaten seit Rechtskraft seines Urteils, um die Schweiz zu verlassen. C.-Mit Verwaltungsgerichtsbeschwerde vom 7. September 1999 beantragen A.S._ und B.S._, den Rekursentscheid des Verwaltungsgerichts und den diesem zu Grunde liegenden Beschwerdeentscheid des Justiz-, Polizei- und Sanitätsdepartements sowie die Verfügung der Fremdenpolizei vom 16. November 1998 aufzuheben. Das Justiz-, Polizei- und Sanitätsdepartement sowie das Verwaltungsgericht des Kantons Graubünden beantragen, die Beschwerde abzuweisen, soweit darauf einzutreten sei. Das Bundesamt für Ausländerfragen stellt im Auftrag des Eidgenössischen Justiz- und Polizeidepartements den Antrag, die Beschwerde abzuweisen. D.-Mit Verfügung vom 30. September 1999 hat der Abteilungspräsident der Beschwerde aufschiebende Wirkung zuerkannt.