Search

The class of maps on a surface of genus g > 0 such that each point belongs to at most k ≥ 3 regions is studied. The problem is to estimate in terms of g and k the chromatic number of such a map (it is assumed that the regions having a common point must have distinct colors). In general case, an upper bound of the chromatic number is established. For k = 4, it is proved that the problem is equivalent to finding the maximal chromatic number for analogs of 1 -planar graphs on a surface of genus g. In this case, a more strong bound is obtained and a method of constructing examples, for which this bound is achieved, is presented. In addition, for analogs of 2-planar graphs on a surface of genus g, an upper bound on maximal chromatic number is proved. Bibliography: 8 titles., UDC 519.173.2, 519.174.7 1. INTRODUCTION One of the oldest problems in graph theory is to establish a connection between the chromatic number of a graph and the possibility of embedding [...]

Let G be a graph that can be drawn on a plane in such a way that any edge intersects at most one other edge. It is proved that the chromatic number of G does not exceed 7. The bound x(G) ≤ 9 + 17 + 64g/2 is also proved for a graph G that can be drawn on a surface of genus g (g ≥ 1) in such a way that any edge intersects at most one other edge. Bibliography: 8 titles., UDC 519.173.2, 519.174.7 1. INTRODUCTION Questions concerning the relationship between the chromatic number of a graph and the existence of its drawing on a surface are among the oldest problems [...]

Let D be a strongly connected digraph on n [greater than or equal to] 4 vertices. A vertex v of D is noncritical if the digraph D - v is strongly connected. It is proved that if the sum of degrees of any two adjacent vertices of D is at least n + l, then there exists a noncritical vertex in D, and if the sum of degrees of any two adjacent vertices of D is at least n + 2, then there exist two noncritical vertices in D. A series of examples confirms that these bounds are tight. Bibliography: 4 titles., UDC 519.172.3 1. Introduction In this paper, we consider a digraph D without loops and multiple arcs, i.e., any two vertices x and y are connected by at most two [...]

Let G be a circle graph without clique on 4 vertices. We prove that the chromatic number of G does not exceed 30. Bibliography: 7 titles., UDC 519.174.7 1. INTRODUCTION Definition 1. Fix a circle. Let π he a finite set of chords of this circle. A circle graph G(A) is a graph with π as [...]