Colouring negative exact-distance graphs of signed graphs
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914835429588992 |
|---|---|
| author | Naserasr, Reza de Mendez, Patrice Ossona Quiroz, Daniel A. Šámal, Robert Yu, Weiqiang |
| author_facet | Naserasr, Reza de Mendez, Patrice Ossona Quiroz, Daniel A. Šámal, Robert Yu, Weiqiang |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2406_10780 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Colouring negative exact-distance graphs of signed graphs Naserasr, Reza de Mendez, Patrice Ossona Quiroz, Daniel A. Šámal, Robert Yu, Weiqiang Combinatorics 05C10, 05C12, 05C15, 05C22, 05C60 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. |
| title | Colouring negative exact-distance graphs of signed graphs |
| topic | Combinatorics 05C10, 05C12, 05C15, 05C22, 05C60 |
| url | https://arxiv.org/abs/2406.10780 |