Speaker : 1. Prof. Huang, Kuo-Ching (Providence University) 2. Prof. Hsin-Hao Lai (National Kaohsiung Normal University)
Title : 1. On the Near-factor-critical Graphs 2. An Intorduction of Entropy Compression
Time : 2014-05-09 (Fri) 14:00 - 16:15
Place : Seminar Room 617, Institute of Mathematics (NTU Campus)
Abstract: 1. A near-factor of a finite simple graph is a matching that saturates all vertices except one. A graph is said to be near-factor-critical if the deletion of any vertex from results in a subgraph that has a near-factor. We prove that a connected graph is near-factor-critical if and only if it has a perfect matching. We also characterize disconnected near-factor-critical graphs. 2. The entropy compression is a new developed and inspiring method. And it was widely discussed by combinatorists. For example, see [6]. In this talk, I will describe the idea behind the method. Also, I will introduce the results obtained by entropy compression and sketch their proofs in [1],[2],[3],[5].
References: [1] V. Dujmovic, G. Joret, J. Kozik, D. R. Wood, Nonrepetitive colouring via entropy compression, arXiv:1112.5524, 2012. [2] J. Grytczuk, J. Kozik, P. Micek, New approach to nonrepetitive sequences, Random Structures Algorithms 42 (2013), 214-225. [3] L. Esperet, A. Parreau, Acyclic edge-coloring using entropy compression, Eu- ropean J. Combin. 34 (2013), 1019-1027. [4] R. Moser, G. Tardos, A constructive proof of the general Lovasz local lemma, J. ACM 57 (2010), Art. 11. [5] Jakub Przyby lo, On the Facial Thue Choice Index via Entropy Compression, J. Graph Theory, DOI: 10.1002/jgt.21781. [6] T. Tao, Mosers entorpy compression argument (blog post), available at: http://terrytao.wordpress.com/2009/08/05/mosers-entropy-compression- argument/.