On f-edge cover-coloring of simple graphs

Wang Jihui; Zhang Sumei; Hou Jianfeng

On f-edge cover-coloring of simple graphs

Wang Jihui^*, Zhang Sumei, Hou Jianfeng

^*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

4 Citations (Scopus)

Abstract

Let G(V, E) be a simple graph, and let f be an integer function on V with 1 ≤ f(v) ≤ d(v) to each vertex v ε V. An f-edge cover-coloring of a graph G is a coloring of edge set E such that each color appears at each vertex v ε V at least f(v) times. The f-edge cover chromatic index of G, denoted by χ′_fc(G), is the maximum number of colors such that an f-edge cover-coloring of G exists. Any simple graph G has f-edge cover chromatic index equal to δ_f or δ_f-1, where δ_f = min vεV{[d(v/f(v]}. If χ′_fc(G) = δ_f, then G is of C_f I class; otherwise G is of C_f II class. In this paper, we give some sufficient conditions for a graph to be of C_f I class, and discuss the classification problem of complete graphs on f-edge cover-coloring.

Original language	English
Title of host publication	Computational Science - ICCS 2007 - 7th International Conference, Proceedings
Pages	448-452
Number of pages	5
Edition	PART 3
Publication status	Published - 2007
Externally published	Yes
Event	7th International Conference on Computational Science, ICCS 2007 - Beijing, China Duration: 27 May 2007 → 30 May 2007

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Number	PART 3
Volume	4489 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	7th International Conference on Computational Science, ICCS 2007
Country/Territory	China
City	Beijing
Period	27/05/07 → 30/05/07

Keywords

Edge-coloring
Simple graph
f-edge cover-coloring

Cite this

@inproceedings{cc452893c7184c0bb9b7229acdf059b1,

title = "On f-edge cover-coloring of simple graphs",

abstract = "Let G(V, E) be a simple graph, and let f be an integer function on V with 1 ≤ f(v) ≤ d(v) to each vertex v ε V. An f-edge cover-coloring of a graph G is a coloring of edge set E such that each color appears at each vertex v ε V at least f(v) times. The f-edge cover chromatic index of G, denoted by χ′fc(G), is the maximum number of colors such that an f-edge cover-coloring of G exists. Any simple graph G has f-edge cover chromatic index equal to δf or δf-1, where δf = min vεV{[d(v/f(v]}. If χ′fc(G) = δf, then G is of Cf I class; otherwise G is of Cf II class. In this paper, we give some sufficient conditions for a graph to be of Cf I class, and discuss the classification problem of complete graphs on f-edge cover-coloring.",

keywords = "Edge-coloring, Simple graph, f-edge cover-coloring",

author = "Wang Jihui and Zhang Sumei and Hou Jianfeng",

year = "2007",

language = "English",

isbn = "9783540725879",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

number = "PART 3",

pages = "448--452",

booktitle = "Computational Science - ICCS 2007 - 7th International Conference, Proceedings",

edition = "PART 3",

note = "7th International Conference on Computational Science, ICCS 2007 ; Conference date: 27-05-2007 Through 30-05-2007",

}

Jihui, W, Sumei, Z & Jianfeng, H 2007, On f-edge cover-coloring of simple graphs. in Computational Science - ICCS 2007 - 7th International Conference, Proceedings. PART 3 edn, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), no. PART 3, vol. 4489 LNCS, pp. 448-452, 7th International Conference on Computational Science, ICCS 2007, Beijing, China, 27/05/07.

On f-edge cover-coloring of simple graphs. / Jihui, Wang; Sumei, Zhang; Jianfeng, Hou.
Computational Science - ICCS 2007 - 7th International Conference, Proceedings. PART 3. ed. 2007. p. 448-452 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4489 LNCS, No. PART 3).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - On f-edge cover-coloring of simple graphs

AU - Jihui, Wang

AU - Sumei, Zhang

AU - Jianfeng, Hou

PY - 2007

Y1 - 2007

N2 - Let G(V, E) be a simple graph, and let f be an integer function on V with 1 ≤ f(v) ≤ d(v) to each vertex v ε V. An f-edge cover-coloring of a graph G is a coloring of edge set E such that each color appears at each vertex v ε V at least f(v) times. The f-edge cover chromatic index of G, denoted by χ′fc(G), is the maximum number of colors such that an f-edge cover-coloring of G exists. Any simple graph G has f-edge cover chromatic index equal to δf or δf-1, where δf = min vεV{[d(v/f(v]}. If χ′fc(G) = δf, then G is of Cf I class; otherwise G is of Cf II class. In this paper, we give some sufficient conditions for a graph to be of Cf I class, and discuss the classification problem of complete graphs on f-edge cover-coloring.

AB - Let G(V, E) be a simple graph, and let f be an integer function on V with 1 ≤ f(v) ≤ d(v) to each vertex v ε V. An f-edge cover-coloring of a graph G is a coloring of edge set E such that each color appears at each vertex v ε V at least f(v) times. The f-edge cover chromatic index of G, denoted by χ′fc(G), is the maximum number of colors such that an f-edge cover-coloring of G exists. Any simple graph G has f-edge cover chromatic index equal to δf or δf-1, where δf = min vεV{[d(v/f(v]}. If χ′fc(G) = δf, then G is of Cf I class; otherwise G is of Cf II class. In this paper, we give some sufficient conditions for a graph to be of Cf I class, and discuss the classification problem of complete graphs on f-edge cover-coloring.

KW - Edge-coloring

KW - Simple graph

KW - f-edge cover-coloring

UR - http://www.scopus.com/inward/record.url?scp=38149075305&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:38149075305

SN - 9783540725879

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 448

EP - 452

BT - Computational Science - ICCS 2007 - 7th International Conference, Proceedings

T2 - 7th International Conference on Computational Science, ICCS 2007

Y2 - 27 May 2007 through 30 May 2007

ER -

On f-edge cover-coloring of simple graphs

Abstract

Publication series

Conference

Keywords

Other files and links

Fingerprint

Cite this