A game generalizing Hall's theorem

DOI10.1016/J.DISC.2013.12.010MaRDI QIDQ394371zbMATH OpenOpenAlexFDO

Authors Landon Rabern

Publication date 27 January 2014

Published in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

transversaledge coloringHall's theoremSDRVizing's theorem

Mathematics Subject Classification ID

2-person games (91A05) Games on graphs (graph-theoretic aspects) (05C57) Transversal (matching) theory (05D15) Games involving graphs (91A43)

Abstract: We characterize the initial positions from which the first player has a winning strategy in a certain two-player game. This provides a generalization of Hall's theorem. Vizing's edge coloring theorem follows from a special case.

Recommendations

• Hall's theorem revisited
• scientific article; zbMATH DE number 1354920
• A generalization of Hall's theorem for \(k\)-uniform \(k\)-partite hypergraphs
• Hall's and Kőnig's theorem in graphs and hypergraphs
• Extending Hall's theorem into list colorings: a partial history

Cites work

• A new method of proving theorems on chromatic index
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Graph edge coloring. Vizing's theorem and Goldberg's conjecture
• List edge and list total colourings of multigraphs
• The list chromatic index of a bipartite multigraph

Cited in

(4)

• The Cinderella Game on Holes and Anti-holes
• A generalization of the blind rotating table game
• scientific article; zbMATH DE number 6490905 (Why is no real title available?)
• Special issue in honour of Landon Rabern

This page was built for publication: A game generalizing Hall's theorem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q394371)