Proper connection of graphs

被引：93

作者：

Borozan, Valentin ^{[2
]}

Fujita, Shinya ^{[1
]}

Gerek, Aydin ^{[3
]}

Magnant, Colton ^{[3
]}

Manoussakis, Yannis ^{[2
]}

Montero, Leandro ^{[2
]}

Tuza, Zsolt ^{[2
,4
,5
]}

机构：

[1] Gunma Natl Coll Technol, Dept Math, Maebashi, Gunma 3718530, Japan

[2] Univ Paris 11, LRI, F-91405 Orsay, France

[3] Lehigh Univ, Dept Math, Bethlehem, PA 18015 USA

[4] Hungarian Acad Sci, Alfred Renyi Inst Math, H-1053 Budapest, Hungary

[5] Univ Pannonia, Dept Comp Sci & Syst Technol, H-8200 Veszprem, Hungary

来源：

DISCRETE MATHEMATICS | 2012年 / 312卷 / 17期

基金：

日本学术振兴会; 匈牙利科学研究基金会;

关键词：

Proper coloring; Proper connection; RAINBOW CONNECTION; PATHS; CYCLES;

D O I：

10.1016/j.disc.2011.09.003

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

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 Pc-k(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 pc(k)(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 pc(1) (G) = 2. (C) 2011 Elsevier B.V. All rights reserved.

引用

页码：2550 / 2560

页数：11

共 17 条

[1] Cycles and Paths in Edge-Colored Graphs with Given Degrees [J].

Abouelaoualim, A. ;

Das, Kinkar Ch. ;

de la Vega, W. Fernandez ;

Karpinski, M. ;

Manoussakis, Y. ;

Martinhon, C. A. ;

Saad, R. .

JOURNAL OF GRAPH THEORY, 2010, 64 (01) :63-86

[2]

[Anonymous], PERIOD MATH HUNGAR

[3]

[Anonymous], 1952, Proceedings of the London Mathematical Society, DOI [10.1112/plms/s3-2.1.69, DOI 10.1112/PLMS/S3-2.1.69]

[4] Alternating cycles and paths in edge-coloured multigraphs: A survey [J].

BangJensen, J ;

Gutin, G .

DISCRETE MATHEMATICS, 1997, 165 :39-60

[5]

Caro Y, 2008, ELECTRON J COMB, V15

[6]

Chartrand G., 2007, Congr. Numer, V184, P209

[7]

Chartrand G, 2008, MATH BOHEM, V133, P85

[8] Rainbow paths [J].

Dellamonica, Domingos, Jr. ;

Magnant, Colton ;

Martin, Daniel M. .

DISCRETE MATHEMATICS, 2010, 310 (04) :774-781

[9] RELATIVE LENGTH OF LONG PATHS AND CYCLES IN GRAPHS WITH LARGE DEGREE SUMS [J].

ENOMOTO, H ;

VANDEHEUVEL, J ;

KANEKO, A ;

SAITO, A .

JOURNAL OF GRAPH THEORY, 1995, 20 (02) :213-225

[10] Properly colored paths and cycles [J].

Fujita, Shinya ;

Magnant, Colton .

DISCRETE APPLIED MATHEMATICS, 2011, 159 (14) :1391-1397

← 1 2 →