Accéder directement au contenu Accéder directement à la navigation

# On the signed chromatic number of some classes of graphs

1 COATI - Combinatorics, Optimization and Algorithms for Telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , Laboratoire I3S - COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
6 GOAL - Graphes, AlgOrithmes et AppLications
LIRIS - Laboratoire d'InfoRmatique en Image et Systèmes d'information
Abstract : A signed graph $(G, \sigma)$ is a graph $G$ along with a function $\sigma: E(G) \to \{+,-\}$. A closed walk of a signed graph is positive (resp., negative) if it has an even (resp., odd) number of negative edges, counting repetitions. A homomorphism of a (simple) signed graph to another signed graph is a vertex-mapping that preserves adjacencies and signs of closed walks. The signed chromatic number of a signed graph $(G, \sigma)$ is the minimum number of vertices $|V(H)|$ of a signed graph $(H, \pi)$ to which $(G, \sigma)$ admits a homomorphism. Homomorphisms of signed graphs have been attracting growing attention in the last decades, especially due to their strong connections to the theories of graph coloring and graph minors. These homomorphisms have been particularly studied through the scope of the signed chromatic number. In this work, we provide new results and bounds on the signed chromatic number of several families of signed graphs (planar graphs, triangle-free planar graphs, $K_n$-minor-free graphs, and bounded-degree graphs).
Keywords :
Type de document :
Article dans une revue

Littérature citée [28 références]

https://hal.archives-ouvertes.fr/hal-02947399
Contributeur : Julien Bensmail Connectez-vous pour contacter le contributeur
Soumis le : jeudi 24 septembre 2020 - 08:03:33
Dernière modification le : lundi 20 décembre 2021 - 16:50:13
Archivage à long terme le : : jeudi 3 décembre 2020 - 16:27:21

### Fichiers

main.pdf
Fichiers produits par l'(les) auteur(s)

### Identifiants

• HAL Id : hal-02947399, version 1
• ARXIV : 2009.12059

### Citation

Julien Bensmail, Sandip Das, Soumen Nandi, Théo Pierron, Sagnik Sen, et al.. On the signed chromatic number of some classes of graphs. Discrete Mathematics, Elsevier, inPress. ⟨hal-02947399v1⟩

### Métriques

Les métriques sont temporairement indisponibles