Cycle Spectra of Graphs

循环的概念是图论中最重要和最基本的概念之一。图中周期的许多方面已经受到了广泛的关注，近年来出现了一些新的和具有挑战性的研究方向，即所谓的图的周期谱，即图的周期长度的集合。我们的研究重点将放在丰富循环谱的充要条件上，即存在不同长度的循环的充要条件。这类经典的充分条件一般在相当密集的图中成立，稀疏图的循环谱值得进一步研究。富循环谱的必要条件以相反的方式更方便地研究：缺乏富循环谱或某些周期长度对其他图理论性质的影响是什么？最近，人们设计了强大的（概率）方法来研究循环长度与同态、着色、独立集或支配集之间的相互作用。

One of the most important and basic graph theoretical concepts is the notion of a cycle. While many aspects of cycles in graphs have already received much attention, several new and challenging research directions concerning the so-called cycle spectrum of a graph, dened as the set of its cycle lengths, emerged during recent years. The focus of our research will be on necessary and sufficient conditions which imply a rich cycle spectrum, i.e. which imply the existence of cycles of different lengths. Classical sufficient conditions of this type typically hold in rather dense graphs and the cycle spectrum of sparse graphs deserves further investigation. Necessary conditions for a rich cycle spectrum are more conveniently studied in contraposition: What is the impact of the absence of a rich cycle spectrum or of certain cycle lengths on other graph theoretical properties? Recently, powerful (probabilistic) methods have been devised to study the interplay between cycle lengths on the one hand and for instance homomorphisms, colourings, independent sets or dominating sets on the other hand.