General antifactors of graphs
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.
- Good characterizations for some degree constrained subgraphs
- Matchings with lower quotas: algorithms and complexity
- A \(\frac{1}{2}\)-integral relaxation for the \(A\)-matching problem
- Degree constrained subgraphs
- Antifactors of regular bipartite graphs
- Editing graphs to satisfy degree constraints: a parameterized approach
- 3-Regular subgraphs and (3,1)-colorings of 4-regular pseudographs
- A Tutte-type characterization for graph factors
- Optimal general factor problem and jump system intersection
- AntiFactor is FPT parameterized by treewidth and list size (but counting is hard)
- Recognition complexity of subgraphs of \({\mathbf{k}}\)-connected planar cubic graphs
- Anti-factor is FPT parameterized by treewidth and list size (but counting is hard)
- Efficient recognition of subgraphs of planar cubic bridgeless graphs
- Optimal general factor problem and jump system intersection
- Finding a maximum restricted \(t\)-matching via Boolean edge-CSP
- Matchings: source, goal, and faithful companion
This page was built for publication: General antifactors of graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1325259)
