Homomorphisms of 2-Edge-Colored Graphs

Amanda Montejano; Pascal Ochem; Alexandre Pinlou; André Raspaud; Eric Sopena

Homomorphisms of 2-Edge-Colored Graphs

Amanda Montejano ¹ Pascal Ochem ² Alexandre Pinlou ^{3, *} André Raspaud ⁴ Eric Sopena ⁴

* Auteur correspondant

1 Applied Mathematics IV Department

2 LRI - Laboratoire de Recherche en Informatique

3 ALGCO - Algorithmes, Graphes et Combinatoire

LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier

4 LaBRI - Laboratoire Bordelais de Recherche en Informatique

Abstract : In this paper, we study homomorphisms of 2-edge-colored graphs, that is graphs with edges colored with two colors. We consider various graph classes (outerplanar graphs, partial 2-trees, partial 3-trees, planar graphs, graphs with bounded maximum average degree) and the problem is to find, for each class, the smallest number of vertices of a 2-edge-colored graph H such that each graph of the considered class admits a homomorphism to H.

Type de document :

Rapport

RR-08008, 2008, pp.26

Domaine :

Informatique [cs] / Mathématique discrète [cs.DM]

Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00266540
Contributeur : Alexandre Pinlou <>
Soumis le : lundi 24 mars 2008 - 16:27:19
Dernière modification le : jeudi 24 mai 2018 - 15:59:22

Homomorphisms of 2-Edge-Colored Graphs

Identifiants

Collections

Citation

Exporter

Métriques

180

Contact

Homomorphisms of 2-Edge-Colored Graphs

Identifiants

Collections

Citation

Exporter

Partager

Métriques

180

Contact