A note on [r, s, c, t]-colorings of graphs

Jian Ting Sheng, Gui Zhen Liu

Research output: Contribution to journalArticlepeer-review

Abstract

Let G be a simple graph with vertex set V (G) and edge set E(G). A subset S of V (G) is called an independent set if no two vertices of S are adjacent in G. The minimum number of independent sets which form a partition of V (G) is called chromatic number of G, denoted by χ(G). A subset S of E(G) is called an edge cover of G if the subgraph induced by S is a spanning subgraph of G. The maximum number of edge covers which form a partition of E(G) is called edge covering chromatic number of G, denoted by χ′c(G). Given nonnegative integers r, s, t and c, an [r, s, c, t]-coloring of G is a mapping f from V (G)∪(G) to the color set {0, 1,..., k-1} such that the vertices with the same color form an independent set of G, the edges with the same color form an edge cover of G, and {pipe}f(vi)-f(vj){pipe} ≥ r if vi and vj are adjacent, {pipe}f(ei)-f(ej){pipe} ≥ s for every ei, ej from different edge covers, {pipe}f(vi) - f(ej){pipe} ≥ t for all pairs of incident vertices and edges, respectively, and the number of edge covers formed by the coloring of edges is exactly c. The [r, s, c, t]-chromatic number χr;s;c;t(G) of G is deffined to be the minimum k such that G admits an [r, s, c, t]-coloring. In this paper, we present the exact value of χr,s,c,t(G) when δ(G) = 1 or G is an even cycle.

Original languageEnglish (US)
Pages (from-to)165-169
Number of pages5
JournalBulletin of the Malaysian Mathematical Sciences Society
Volume34
Issue number1
StatePublished - 2011

Keywords

  • Chromatic number
  • Edge covering coloring
  • [r, s, c, t]-coloring
  • [r, s, t]-coloring

ASJC Scopus subject areas

  • Mathematics(all)

Fingerprint

Dive into the research topics of 'A note on [r, s, c, t]-colorings of graphs'. Together they form a unique fingerprint.

Cite this