The -th exact-distance graph, of a graph has as its vertex set, and as an edge if and only if the distance between and is (exactly) in . We consider two possible extensions of this notion for signed graphs. Finding the chromatic number of a negative exact-distance square of a signed graph is a weakening of the problem of finding the smallest target graph to which the signed graph has a sign-preserving homomorphism. We study the chromatic number of negative exact-distance graphs of signed graphs that are planar, and also the relation of these chromatic numbers with the generalised colouring numbers of the underlying graphs. Our results are related to a theorem of Alon and Marshall about homomorphisms of signed graphs.

生成讲解博客的中文版本

生成AI智能校验的中文版本