首页 | 本学科首页   官方微博 | 高级检索  
     检索      


Chromatic coloring with a maximum color class
Authors:Bor-Liang Chen  Chih-Hung Yen
Institution:a Department of Business Administration, National Taichung Institute of Technology, Taichung 40401, Taiwan
b Department of Applied Mathematics, Providence University, Shalu, Taichung 43301, Taiwan
c Department of Applied Mathematics, National Chiayi University, Chiayi 60004, Taiwan
Abstract:Let G be any graph, and also let Δ(G), χ(G) and α(G) denote the maximum degree, the chromatic number and the independence number of G, respectively. A chromatic coloring of G is a proper coloring of G using χ(G) colors. A color class in a proper coloring of G is maximum if it has size α(G). In this paper, we prove that if a graph G (not necessarily connected) satisfies χ(G)≥Δ(G), then there exists a chromatic coloring of G in which some color class is maximum. This cannot be guaranteed if χ(G)<Δ(G). We shall also give some other extensions.
Keywords:Vertex coloring  Chromatic coloring  Maximum degree  Chromatic number  Independence number
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号