The k-th exact-distance graph, of a graph G has $V(G)$ as its vertex set, and $xy$ as an edge if and only if the distance between x and y is (exactly) k in G. 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.
No takes yet. Share an insight, caveat, or question.
Naserasr et al. (2024) studied this question.
Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context: