A Note on Semi-coloring of Graphs

被引：1

作者：

Wu, Baoyindureng ^{[1
]}

Deng, Xingchao ^{[2
]}

An, Xinhui ^{[1
]}

Yan, Guiying ^{[3
]}

机构：

[1] Xinjiang Univ, Coll Math & Syst Sci, Urumqi 830046, Xinjiang, Peoples R China

[2] LPMC TJKLC Nankai Univ, Ctr Combinator, Tianjin 300071, Peoples R China

[3] Chinese Acad Sci, Acad Math & Syst Sci, Beijing 830046, Peoples R China

来源：

GRAPHS AND COMBINATORICS | 2013年 / 29卷 / 04期

关键词：

Edge coloring; Factor; Matching; Semi-coloring;

D O I：

10.1007/s00373-012-1171-1

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

Semi-coloring is a new type of edge coloring of graphs. In this note, we show that every graph has a semi-coloring. This answers a problem, posed by Daniely and Linial, in affirmative. It implies that every r-regular graph has at least different {K (2), C (i) | i a parts per thousand yen 3}-factors.

引用

页码：1135 / 1140

页数：6

共 12 条

[1] FACTORS AND FACTORIZATIONS OF GRAPHS - A SURVEY [J].

AKIYAMA, J ;

KANO, M .

JOURNAL OF GRAPH THEORY, 1985, 9 (01) :1-42

[2]

[Anonymous], 1986, MATCHING THEORY

[3]

[Anonymous], 2001, Introduction to Graph Theory

[4]

Babler F., 1938, COMMENT MATH HELV, V10, P275

[5]

Daniely A, J GRAPH THEORY, DOI [10.1002/jgt.20593, DOI 10.1002/JGT.20593]

[6]

Petersen J., 1891, ACTA MATH, V15, P193, DOI [DOI 10.1007/BF02392606, 10.1007/BF02392606]

[7] Graph factors and factorization: 1985-2003: A survey [J].

Plummer, Michael D. .

DISCRETE MATHEMATICS, 2007, 307 (7-8) :791-821

[8]

Sheinerman E.R, 1997, FRACTIONAL GRAPH THE

[9]

Steinparz F, 1982, C GRAPH THEOR CONC C

[10] THE 1-FACTORS OF ORIENTED GRAPHS [J].

TUTTE, WT .

PROCEEDINGS OF THE AMERICAN MATHEMATICAL SOCIETY, 1953, 4 (06) :922-931

← 1 2 →