equitable coloring of graph products

;Hanna Furmańczyk
zhonghua yi xue za zhi 2006 Vol. 26 pp. 31-44
140
furmaczyk2006opusculaequitable

Abstract

A graph is equitably \(k\)-colorable if its vertices can be partitioned into \(k\) independent sets in such a way that the number of vertices in any two sets differ by at most one. The smallest \(k\) for which such a coloring exists is known as the equitable chromatic number of \(G\) and denoted by \(\chi_{=}(G)\). It is interesting to note that if a graph \(G\) is equitably \(k\)-colorable, it does not imply that it is equitably \((k+1)\)-colorable. The smallest integer \(k\) for which \(G\) is equitably \(k'\)-colorable for all \(k'\geq k\) is called the equitable chromatic threshold of \(G\) and denoted by \(\chi_{=}^{*}(G)\). In the paper we establish the equitable chromatic number and the equitable chromatic threshold for certain products of some highly-structured graphs. We extend the results from [Chen B.-L., Lih K.-W., Yan J.-H., Equitable coloring of graph products, manuscript, 1998] for Cartesian, weak and strong tensor products.

Citation

ID: 151138
Ref Key: furmaczyk2006opusculaequitable
Use this key to autocite in SciMatic or Thesis Manager

References

Blockchain Verification

Account:
NFT Contract Address:
0x95644003c57E6F55A65596E3D9Eac6813e3566dA
Article ID:
151138
Unique Identifier:
Network:
Scimatic Chain (ID: 481)
Loading...
Blockchain Readiness Checklist
Authors
Abstract
Journal Name
Year
Title
5/5
Creates 1,000,000 NFT tokens for this article
Token Features:
  • ERC-1155 Standard NFT
  • 1 Million Supply per Article
  • Transferable via MetaMask
  • Permanent Blockchain Record
Blockchain QR Code
Scan with Saymatik Web3.0 Wallet

Saymatik Web3.0 Wallet