Open AccessPerfect matchings in graphs with prescribed local restrictions
Author(s) -
П. А. Иржавский,
Ю. Л. Орловичã
Publication year - 2019
Publication title -
doklady nacionalʹnoj akademii nauk belarusi
Language(s) - English
Resource type - Journals
eISSN - 2524-2431
pISSN - 1561-8323
DOI - 10.29235/1561-8323-2019-63-4-408-420
Subject(s) - combinatorics , perfect graph theorem , mathematics , vertex (graph theory) , trivially perfect graph , graph , line graph , discrete mathematics , strong perfect graph theorem , 1 planar graph , pathwidth
A graph is called K 1, p -restricted ( p ≥ 3) if for every vertex of the graph there are at least p - 2 edges between any p neighbours of the vertex. In this article, new sufficient conditions for existence of a perfect matching in K 1,p -restricted graphs are established. In particular, J. Petersen’s classical result that every 2-edge connected 3-regular graph contains a perfect matching follows from these conditions.