INDUCED MATCHINGS IN CUBIC GRAPHS

被引：105

作者：

HORAK, P

QING, H

TROTTER, WT

机构：

[1] ARIZONA STATE UNIV,DEPT MATH,TEMPE,AZ 85287

[2] BELL COMMUN RES INC,MORRISTOWN,NJ

来源：

JOURNAL OF GRAPH THEORY | 1993年 / 17卷 / 02期

关键词：

D O I：

10.1002/jgt.3190170204

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

In this paper, we show that the edge set of a cubic graph can always be partitioned into 10 subsets, each of which induces a matching in the graph. This result is a special case of a general conjecture made by Erdos and Nesetril: For each d greater-than-or-equal-to 3, the edge set of a graph of maximum degree d can always be partitioned into right perpendicular 5d2/4 left perpendicular subsets each of which induces a matching.

引用

页码：151 / 160

页数：10

共 8 条

[1]

ANDERSEN LD, IN PRESS ANN DISCRET

[2] INDUCED MATCHINGS [J].

CAMERON, K .

DISCRETE APPLIED MATHEMATICS, 1989, 24 (1-3) :97-102

[3] THE MAXIMUM NUMBER OF EDGES IN 2K2-FREE GRAPHS OF BOUNDED DEGREE [J].

CHUNG, FRK ;

GYARFAS, A ;

TUZA, Z ;

TROTTER, WT .

DISCRETE MATHEMATICS, 1990, 81 (02) :129-135

[4] PROBLEMS AND RESULTS IN COMBINATORIAL ANALYSIS AND GRAPH-THEORY [J].

ERDOS, P .

DISCRETE MATHEMATICS, 1988, 72 (1-3) :81-92

[5] INDUCED MATCHINGS IN BIPARTITE GRAPHS [J].

FAUDREE, RJ ;

GYARFAS, A ;

SCHELP, RH ;

TUZA, Z .

DISCRETE MATHEMATICS, 1989, 78 (1-2) :83-87

[6]

FAUDREE RT, UNPUB STRONG CHROMAT

[7]

Hall P, 1935, J LOND MATH SOC, V10, P26, DOI DOI 10.1112/JLMS/S1-10.37.26

[8]

HORAK P, UNPUB STRONG CHROMAT

← 1 →