|
|||||
|
|
Homomorphisms of 2-edge-colored graphs |
|
| Authors: | Amanda Montejano Alexandre Pinlou André Raspaud Éric Sopena |
| Institution: | a Department Matemàtica Aplicada IV, Universitat Polytècnica de Catalunya, Barcelone, Spain b CNRS, Lab. J.V. Poncelet, LRI, Bât 490, Université Paris-Sud 11, 91405 Orsay Cedex, France c CNRS, LIRMM, Université Montpellier 2, 161 rue Ada, 34392 Montpellier Cedex 5, France d LaBRI, Université Bordeaux 1, 351 Cours de la Libération, 33405 Talence, 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) 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. |
| Keywords: | Graph coloring Homomorphism Outerplanar graph Partial _method=retrieve& _eid=1-s2 0-S0166218X09003709& _mathId=si39 gif& _pii=S0166218X09003709& _issn=0166218X& _acct=C000054348& _version=1& _userid=3837164& md5=4d1786d760d2a131adb468b66b58cff7')" style="cursor:pointer k-tree" target="_blank">" alt="Click to view the MathML source" title="Click to view the MathML source">k-tree Planar graph Girth Discharging procedure Maximum average degree |
| 本文献已被 ScienceDirect 等数据库收录！ | |