Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí Department of Mathematic dành cho các bạn yêu thích môn toán học đề tài: On the sharpness of some results relating cuts and crossing numbers. | On the sharpness of some results relating cuts and crossing numbers Laurent Beaudou Drago Bokal Institut Fourier Fakulteta za naravoslovje in matematiko Universite Joseph Fourier Univerza v Mariboru Grenoble France Maribor Slovenija Submitted Feb 27 2009 Accepted Jun 28 2010 Published Jul 10 2010 Mathematics Subject Classifications 05C10 Abstract It is already known that for very small edge cuts in graphs the crossing number of the graph is at least the sum of the crossing number of slightly augmented components resulting from the cut. Under stronger connectivity condition in each cut component that was formalized as a graph operation called zip product a similar result was obtained for edge cuts of any size and a natural question was asked whether this stronger condition is necessary. In this paper we prove that the relaxed condition is not sufficient when the size of the cut is at least four and we prove that the gap can grow quadratically with the cut size. 1 Introduction Crossing number of graphs see 13 for basic definitions has been extensively studied for about sixty years and is still a notorious problem in graph theory. While determining or bounding the crossing number of graphs used to be the main issue at the beginning the focus is now shifting to structural aspects of the crossing number problem. These include the study of several variants of crossing number 5 8 18 19 21 22 crossing-critical graphs 9 23 24 or the properties of drawings with a bounded number of crossings per edge 20 . Very early at the development of the crossing number theory Leighton realized that cuts in graphs play an important role in determining the crossing number of a graph. Combining them with the Lipton-Tarjan planar separator theorem 17 he used edge Supported in part by the Ministry of Education Science and Sport of Slovenia Research Program P1-0297 and Research Projects L1-9338 and J1-2043. THE ELECTRONIC JOURNAL OF .
