General antifactors of graphs (Q1325259)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | General antifactors of graphs |
scientific article |
Statements
General antifactors of graphs (English)
0 references
30 June 1994
0 references
In a superstitious company everybody has numbers that he thinks to be unlucky for himself. When they meet, everybody wants to shake hands with some of his acquaintances, but nobody wants to shake hands with an unlucky number of acquaintances. When can this be successful? This question occurred to \textit{L. Lovász} [Period. Math. Hung. 4, No. 2-3, 121-123 (1973; Zbl 0277.05130)], where the case when everyone has one unlucky number (antifactor problem) is answered. In this paper we give a ``Tutte-type good characterization'' (and a simple polynomial algorithm) to decide this question when several unlucky numbers are allowed, but no one in the company has two neighboring unlucky numbers.
0 references
antifactor problem
0 references
good characterization
0 references
polynomial algorithm
0 references