Generalized Topological Essentiality and Coincidence Points of Multivalued Maps

A concept of generalized topological essentiality for a large class of multivalued maps in topological vector Klee admissible spaces is presented. Some direct applications to differential equations are discussed. Using the inverse systems approach the coincidence point sets of limit maps are examined. The main motivation as well as main aim of this note is a study of fixed points of multivalued maps in Fréchet spaces. The approach presented in the paper allows to check not only the nonemptiness of the fixed point set but also its topological structure.      

Periodic Trajectories and Coincidence Points of Tuples of Set-Valued Maps

A fixed-point theorem is proved for a finite composition of set-valued Lipschitz maps such that the product of their Lipschitz constants is less than 1. The notion of a Lipschitz tuple of (finitely many) set-valued maps is introduced; it is proved that such a tuple has a periodic trajectory, which determines a fixed point of the given composition of set-valued Lipschitz maps. This result is applied to study the coincidence points of a pair of tuples (Lipschitz and covering).     

Coincidence Properties for Maps from the Torus to the Klein Bottle

The authors study the coincidence theory for pairs of maps from the Torus to the Klein bottle. Reidemeister classes and the Nielsen number are computed, and it is shown that any given pair of maps satisfies the Wecken property. The 1-parameter Wecken property is studied and a partial negative answer is derived. That is for all pairs of coincidence free maps a countable family of pairs of maps in the homotopy class is constructed such that no two members may be joined by a coincidence free homotopy.     

非紧域上集值映象的重合点与不动点

在赋范线性空间的非空非紧凸集上建立了集值映象对的一个重合点定理,然后用这一定理改进了文献［１］中的集值映象内向集定理与外向集定理,并得到几个集值映象不动点定理．     

The Achromatic Colouring Of Graphs

In this paper, we find out the achromatic number of Central graph of Banana Tree, Helm Graph and Web Graph.     

Saks空间中（A）型相容映射的叠合点及公共不动点（英）

ＣｏｉｎｃｉｄｅｎｃｅＰｏｉｎｔｓａｎｄＣｏｍｍｏｎＦｉｘｅｄＰｏｉｎｔｓｆｏｒＣｏｍｐａｔｉｂｌｅＭａｐｓｏｆＴｙｐｅ（Ａ）ｏｎＳａｋｓＳｐａｃｅｓＰ．Ｐ．Ｍｕｒｔｈｙ，Ｂ．Ｋ．Ｓｈａｒｔｒｉａ，Ｙ．Ｊ．ＣｈｏＣｏｉｎｃｉｄｅｎｃｅＰｏｉｎｔｓａｎ...     

On the Relaxed Colouring Game and the Unilateral Colouring Game

In the paper we introduce the new game—the unilateral \({\mathcal{P}}\) -colouring game which can be used as a tool to study the r-colouring game and the (r, d)-relaxed colouring game. Let be given a graph G, an additive hereditary property \({\mathcal {P}}\) and a set C of r colours. In the unilateral \({\mathcal {P}}\) -colouring game similarly as in the r-colouring game, two players, Alice and Bob, colour the uncoloured vertices of the graph G, but in the unilateral \({\mathcal {P}}\) -colouring game Bob is more powerful than Alice. Alice starts the game, the players play alternately, but Bob can miss his move. Bob can colour the vertex with an arbitrary colour from C, while Alice must colour the vertex with a colour from C in such a way that she cannot create a monochromatic minimal forbidden subgraph for the property \({\mathcal {P}}\) . If after |V(G)| moves the graph G is coloured, then Alice wins the game, otherwise Bob wins. The \({\mathcal {P}}\) -unilateral game chromatic number, denoted by \({\chi_{ug}^\mathcal {P}(G)}\) , is the least number r for which Alice has a winning strategy for the unilateral \({\mathcal {P}}\) -colouring game with r colours on G. We prove that the \({\mathcal {P}}\) -unilateral game chromatic number is monotone and is the upper bound for the game chromatic number and the relaxed game chromatic number. We give the winning strategy for Alice to play the unilateral \({\mathcal {P}}\) -colouring game. Moreover, for k ≥  2 we define a class of graphs \({\mathcal {H}_k =\{G|{\rm every \;block \;of\;}G \; {\rm has \;at \;most}\; k \;{\rm vertices}\}}\) . The class \({\mathcal {H}_k }\) contains, e.g., forests, Husimi trees, line graphs of forests, cactus graphs. Let \({\mathcal {S}_d}\) be the class of graphs with maximum degree at most d. We find the upper bound for the \({\mathcal {S}_2}\) -unilateral game chromatic number for graphs from \({\mathcal {H}_3}\) and we study the \({\mathcal {S}_d}\) -unilateral game chromatic number for graphs from \({\mathcal {H}_4}\) for \({d \in \{2,3\}}\) . As the conclusion from these results we obtain the result for the d-relaxed game chromatic number: if \({G \in \mathcal {H}_k}\) , then \({\chi_g^{(d)}(G) \leq k + 2-d}\) , for \({k \in \{3, 4\}}\) and \({d \in \{0, \ldots, k-1\}}\) . This generalizes a known result for trees.     

Colouring random graphs

We discuss some results concerned with the behaviour of colouring algorithms on large random graphs.     

Colouring series-parallel graphs

We establish a minimax formula for the chromatic index of series-parallel graphs; and also prove the correctness of a greedy algorithm for finding a vertex-colouring of a series-parallel graph.     

Colouring a graph frugally

We prove that any graph with maximum degree sufficiently large, has a proper vertex colouring using +1 colours such that each colour class appears at most log⁸ times in the neighbourhood of any vertex. We also show that for 1, the minimum number of colours required to colour any such graph so that each vertex appears at most times in the neighbourhood of any vertex is (+^1+1//), showing in particular that when =log/loglog, such a colouring cannot always be achieved with O() colours. We also provide a polynomial time algorithm to find such a colouring. This has applications to the total chromatic number of a graph.The second two authors were supported by NATO Collaborative Research Grant #CRG950235.     

Colouring prime distance graphs

Four colours are necessary and sufficient to colour all the integers so that any two with difference equal to a prime have different colours. We investigate the corresponding problem when the setD of prescribed differences is a proper subset of the primes. In particular, we prove that ifD contains {2, 3} and also contains a pair of twin primes (one of which may be 3), then four colours are necessary. Numerous results regarding periodic colourings are also obtained. However, the problem of characterizing those setsD which necessitate four colours remains open.     

Colouring the real line

The problem of colouring the real line so that the distance between like coloured numbers does not lie in some specified set D, called the distance set, is discussed. In particular, the minimum number of colours needed for various distance sets are determined.     

Colouring Clique-Hypergraphs of Circulant Graphs

A clique-colouring of a graph G is a colouring of the vertices of G so that no maximal clique of size at least two is monochromatic. The clique-hypergraph, ${\mathcal{H}(G)}$ , of a graph G has V(G) as its set of vertices and the maximal cliques of G as its hyperedges. A vertex-colouring of ${\mathcal{H}(G)}$ is a clique-colouring of G. Determining the clique-chromatic number, the least number of colours for which a graph G admits a clique-colouring, is known to be NP-hard. In this work, we establish that the clique-chromatic number of powers of cycles is equal to two, except for odd cycles of size at least five, that need three colours. For odd-seq circulant graphs, we show that their clique-chromatic number is at most four, and determine the cases when it is equal to two. Similar bounds for the chromatic number of these graphs are also obtained.