|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)|
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 . 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 ,,,. |
References:  V. Dujmovic, G. Joret, J. Kozik, D. R. Wood, Nonrepetitive colouring via entropy compression, arXiv:1112.5524, 2012.  J. Grytczuk, J. Kozik, P. Micek, New approach to nonrepetitive sequences, Random Structures Algorithms 42 (2013), 214-225.  L. Esperet, A. Parreau, Acyclic edge-coloring using entropy compression, Eu- ropean J. Combin. 34 (2013), 1019-1027.  R. Moser, G. Tardos, A constructive proof of the general Lovasz local lemma, J. ACM 57 (2010), Art. 11.  Jakub Przyby lo, On the Facial Thue Choice Index via Entropy Compression, J. Graph Theory, DOI: 10.1002/jgt.21781.  T. Tao, Mosers entorpy compression argument (blog post), available at: http://terrytao.wordpress.com/2009/08/05/mosers-entropy-compression- argument/.