Homomorphisms of 2-Edge-Colored Graphs

Amanda Montejano 1 Pascal Ochem 2 Alexandre Pinlou 3, * André Raspaud 4 Eric Sopena 4
* 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
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 : mardi 24 avril 2018 - 13:38:59

Identifiants

  • HAL Id : lirmm-00266540, version 1

Collections

LABRI | UNIV-BORDEAUX | UMR8623 | ALGCO | LIRMM | LARA | INRIA | MIPS | TDS-MACS | UNIV-MONTPELLIER

Citation

Amanda Montejano, Pascal Ochem, Alexandre Pinlou, André Raspaud, Eric Sopena. Homomorphisms of 2-Edge-Colored Graphs. RR-08008, 2008, pp.26. 〈lirmm-00266540〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

162

Contact

support.ccsd.cnrs.fr
hal.support@ccsd.cnrs.fr
Logo CCSD