 |
HAL-LIRMM - Open Archive |  |
Reports
Homomorphisms of 2-Edge-Colored Graphs
Amanda Montejano
1
Pascal Ochem
2
Alexandre Pinlou
3, *
André Raspaud
4
Eric Sopena
4
*
Corresponding author
3
ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Amanda Montejano 1
Mail :
Author
Pascal Ochem 2
Mail :
Author IdHAL : pascal-ochem
Alexandre Pinlou 3
Mail : Site :
Correspondent author IdHAL : alexandre-pinlou arXiv : https://arxiv.org/a/alexandre.pinlou@lirmm.fr
André Raspaud 4
Mail :
Author
Eric Sopena 4
Mail :
Author IdHAL : eric-sopena
1
Applied Mathematics IV Department (Barcelona - Spain)
- UPC - Universitat Politècnica de Catalunya [Barcelona] (C./Jordi Girona, 1-3, 08034 Barcelona - Spain)
2
LRI - Laboratoire de Recherche en Informatique (LRI - Bâtiments 650-660 Université Paris-Sud 91405 Orsay Cedex - France)
- CNRS - Centre National de la Recherche Scientifique : UMR8623 (France)
- UP11 - Université Paris-Sud - Paris 11 (Bâtiment 300 - 91405 Orsay cedex - France)
- CentraleSupélec (3, rue Joliot Curie, Plateau de Moulon, 91192 GIF-SUR-YVETTE Cedex - France)
3
ALGCO - Algorithmes, Graphes et Combinatoire (France)
- LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier (161 rue Ada - 34095 Montpellier - France)
- UM - Université de Montpellier : UMR5506 (163 rue Auguste Broussonnet - 34090 Montpellier - France)
- CNRS - Centre National de la Recherche Scientifique : UMR5506 (France)
4
LaBRI - Laboratoire Bordelais de Recherche en Informatique (Domaine Universitaire 351, cours de la Libération 33405 Talence Cedex - France)
- Université Bordeaux Segalen - Bordeaux 2 (146 rue Léo Saignat - 33076 Bordeaux cedex - France)
- Université Sciences et Technologies - Bordeaux 1 (351 cours de la Libération - 33405 Talence cedex - France)
- École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB) (France)
- CNRS - Centre National de la Recherche Scientifique : UMR5800 (France)
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.
Document type :
Reports
Complete list of metadatas
https://hal-lirmm.ccsd.cnrs.fr/lirmm-00266540
Contributor : Alexandre Pinlou <>
Submitted on : Monday, March 24, 2008 - 4:27:19 PM
Last modification on : Tuesday, April 21, 2020 - 1:06:31 AM
Contributor : Alexandre Pinlou <>
Submitted on : Monday, March 24, 2008 - 4:27:19 PM
Last modification on : Tuesday, April 21, 2020 - 1:06:31 AM
Identifiers
- HAL Id : lirmm-00266540, version 1
Collections
LABRI | CNRS | UNIV-BORDEAUX | UMR8623 | ALGCO | LIRMM | LARA | 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⟩
Metrics
Record views
