Proper connection of graphs
| Autor: | Zsolt Tuza, Leandro Montero, Valentin Borozan, Yannis Manoussakis, Colton Magnant, Shinya Fujita, Aydin Gerek |
|---|---|
| Přispěvatelé: | Laboratoire de Recherche en Informatique (LRI), Université Paris-Sud - Paris 11 (UP11)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS), AI Inc. [Kyoto], AI Inc., Laboratoire de l'intégration, du matériau au système (IMS), Université Sciences et Technologies - Bordeaux 1-Institut Polytechnique de Bordeaux-Centre National de la Recherche Scientifique (CNRS), Department of Computer Science and Systems Technology [Veszprem], University of Panninia, Computer and Automation Research Institute [Budapest] (MTA SZTAKI ), Université Sciences et Technologies - Bordeaux 1 (UB)-Institut Polytechnique de Bordeaux-Centre National de la Recherche Scientifique (CNRS) |
| Jazyk: | angličtina |
| Předmět: |
ComputingMethodologies_IMAGEPROCESSINGANDCOMPUTERVISION
0102 computer and information sciences Edge (geometry) [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM] 01 natural sciences Theoretical Computer Science Combinatorics Integer Computer Science::Discrete Mathematics Bounding overwatch Discrete Mathematics and Combinatorics 0101 mathematics Connection (algebraic framework) Computer Science::Data Structures and Algorithms Global structure ComputingMilieux_MISCELLANEOUS Mathematics Discrete mathematics Mathematics::Combinatorics 010102 general mathematics Proper coloring Proper connection Complete coloring Colored 010201 computation theory & mathematics Connection number MathematicsofComputing_DISCRETEMATHEMATICS |
| Zdroj: | Discrete Mathematics Discrete Mathematics, Elsevier, 2012, 312 (17), pp.Pages 2550-2560. ⟨10.1016/j.disc.2011.09.003⟩ Discrete Mathematics, 2012, 312 (17), pp.Pages 2550-2560. ⟨10.1016/j.disc.2011.09.003⟩ |
| ISSN: | 0012-365X |
| DOI: | 10.1016/j.disc.2011.09.003 |
| Popis: | An edge-colored graph G is k-proper connected if every pair of vertices is connected by k internally pairwise vertex-disjoint proper colored paths. The k-proper connection number of a connected graph G, denoted by pck(G), is the smallest number of colors that are needed to color the edges of G in order to make it k-proper connected. In this paper we prove several upper bounds for pck(G). We state some conjectures for general and bipartite graphs, and we prove them for the case when k=1. In particular, we prove a variety of conditions on G which imply pc1(G)=2. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|