On finding constrained independent sets in cycles

DOI10.1007/s00453-023-01179-zarXiv2307.00317OpenAlexW4388342528MaRDI QIDQ6130317

Ishay Haviv

Publication date: 2 April 2024

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2307.00317

zbMATH Keywords

stable setsKneser graphSchrijver graphPPA-completeness

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Graph theory (05Cxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Kneser's conjecture, chromatic number, and homotopy
• A solution to a colouring problem of P. Erdős
• The Hamiltonian property of consecutive-\(d\) digraphs
• On the complexity of the parity argument and other inefficient proofs of existence
• Topological lower bounds for the chromatic number: a hierarchy
• The complexity of finding fair independent sets in cycles
• Computing a small agreeable set of indivisible items
• An algorithm for identifying cycle-plus-triangles graphs
• INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
• The strong chromatic number of a graph
• Equivariant Cohomology and Lower Bounds for Chromatic Numbers
• Combinatorial Nullstellensatz
• INTERSECTING FAMILIES OF SEPARATED SETS
• Fair Representation by Independent Sets
• Drei Sätze über die n-dimensionale euklidische Sphäre
• SOME INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS