Edge-colouring of join graphs

被引：16
作者：
De Simone, C
de Mello, CP [1 ]
机构：
[1] Univ Estadual Campinas, Inst Comp, Campinas, SP, Brazil
[2] CNR, Ist Anal Sistemi & Informat, I-00185 Rome, Italy
来源：
THEORETICAL COMPUTER SCIENCE | 2006年 / 355卷 / 03期
基金：
巴西圣保罗研究基金会;
关键词：
edge-colourings; join gaphs; overfull graphs;
D O I：
10.1016/j.tcs.2005.12.010
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
A join graph is the complete union of two arbitrary graphs. We give sufficient conditions for a join graph to be 1-factorizable. As a consequence of our results, the Hilton's Overfull Subgraph Conjecture holds true for several subclasses of join graphs. (c) 2006 Elsevier B.V. All rights reserved.
引用
收藏
页码：364 / 370
页数：7
相关论文
共 18 条
[1]  
[Anonymous], [No title captured]
[2]   NP-COMPLETENESS OF EDGE-COLORING SOME RESTRICTED GRAPHS [J].
CAI, L ;
ELLIS, JA .
DISCRETE APPLIED MATHEMATICS, 1991, 30 (01) :15-27
[3]  
Chetwynd A. G., 1989, Graph Theory in Memory of G. A. Dirac (Sandbjerg, 1985), vol. 41, P91
[4]   THE CHROMATIC INDEX OF GRAPHS WITH LARGE MAXIMUM DEGREE, WHERE THE NUMBER OF VERTICES OF MAXIMUM DEGREE IS RELATIVELY SMALL [J].
CHETWYND, AG ;
HILTON, AJW .
JOURNAL OF COMBINATORIAL THEORY SERIES B, 1990, 48 (01) :45-66
[5]  
CHETWYND AG, 1985, P LOND MATH SOC, V50, P193
[6]   STAR MULTIGRAPHS WITH 3 VERTICES OF MAXIMUM DEGREE [J].
CHETWYND, AG ;
HILTON, AJW .
MATHEMATICAL PROCEEDINGS OF THE CAMBRIDGE PHILOSOPHICAL SOCIETY, 1986, 100 :303-317
[7]  
Fournier J.-C., 1973, Cah. CERO (Bruxelles), V15, P311
[8]  
Hilton A.J.W., 1987, MATH P CAMBRIDGE PHI, V102, P103
[9]   THE CHROMATIC INDEX OF COMPLETE MULTIPARTITE GRAPHS [J].
HOFFMAN, DG ;
RODGER, CA .
JOURNAL OF GRAPH THEORY, 1992, 16 (02) :159-163
[10]   THE NP-COMPLETENESS OF EDGE-COLORING [J].
HOLYER, I .
SIAM JOURNAL ON COMPUTING, 1981, 10 (04) :718-720
12