6 papers
Optimal b-Colourings and Fall Colourings in -Free Graphs
Jungho Ahn, Tala Eagling-Vose, Felicia Lucke +3
In a colouring of a graph, a vertex is b-chromatic if it is adjacent to a vertex of every other colour. We consider four well-studied colouring problems: b-Chromatic Number, Tight…
Stable Matching with Deviators and Conformists
Frederik Glitzner, David Manlove
In the fundamental Stable Marriage and Stable Roommates problems, there are inherent trade-offs between the size and stability of solutions. While in the former problem, a stable m…
Course Allocation with Credits via Stable Matching
José RodrÃguez, David Manlove
In the {\sc Course Allocation} problem, there are a set of students and a set of courses at a given university. University courses may have different numbers of credits, typically…
A Minimax Perspective on Almost-Stable Matchings
Frederik Glitzner, David Manlove
Stability is crucial in matching markets, yet in many real-world settings - from hospital residency allocations to roommate assignments - full stability is either impossible to ach…
Unsolvability and Beyond in Many-To-Many Non-Bipartite Stable Matching
Frederik Glitzner, David Manlove
We study the Stable Fixtures problem, a many-to-many generalisation of the classical non-bipartite Stable Roommates matching problem. Building on the foundational work of Tan on st…
Perspectives on Unsolvability in the Roommates Problem
Frederik Glitzner, David Manlove
In the well-studied Stable Roommates problem, we seek a stable matching of agents into pairs, where no two agents prefer each other over their assigned partners. However, some inst…