Abstract:
 1. A nearfactor of a finite simple graph $G$ is a matching that saturates all vertices except one. A graph $G$ is said to be nearfactorcritical if the deletion of any vertex from $G$ results in a subgraph that has a nearfactor. We prove that a connected graph $G$ is nearfactorcritical if and only if it has a perfect matching. We also characterize disconnected nearfactorcritical 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), 214225.
[3] L. Esperet, A. Parreau, Acyclic edgecoloring using entropy compression, Eu
ropean J. Combin. 34 (2013), 10191027.
[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/mosersentropycompression
argument/.
