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 等数据库收录! |
|