Max-coloring of vertex-weighted graphs

機構典藏 > College of Sciences > Department of Applied Mathematics and Data Science > Journal Article > Item 987654321/115406

Please use this identifier to cite or link to this item: https://tkuir.lib.tku.edu.tw/dspace/handle/987654321/115406

Title:	Max-coloring of vertex-weighted graphs
Authors:	Hsiang-Chun Hsu;Gerard Jennhwa Chang
Keywords:	Coloring;Weighted graph;Perfection
Date:	2016
Issue Date:	2018-10-25 12:10:59 (UTC+8)
Publisher:	Springer Japan
Abstract:	A proper vertex coloring of a graph G is a partition \{A_1,A_2,\ldots ,A_k\} of the vertex set V(G) into stable sets. For a graph G with a positive vertex-weight c:V(G) \rightarrow (0,\infty ), denoted by (G,c), let \chi (G,c) be the minimum value of \sum _{i=1}^k \max _{v \in A_i} c(v) over all proper vertex coloring \{A_1,A_2,\ldots ,A_k\} of G and \sharp \chi (G,c) the minimum value of k for a proper vertex coloring \{A_1,A_2,\ldots ,A_k\} of G such that \sum _{i=1}^k \max _{v \in A_i} c(v) = \chi (G,c). This paper establishes an upper bound on \sharp \chi (G,c) for a weighted r-colorable graph (G,c), and a Nordhaus–Gaddum type inequality for \chi (G,c). It also studies the c-perfection for a weighted graph (G,c).
Relation:	Graphs and Combinatorics 32(1), p.191-198
DOI:	10.1007/s00373-015-1562-1
Appears in Collections:	[Department of Applied Mathematics and Data Science] Journal Article

Files in This Item:

File	Description	Size	Format
index.html		0Kb	HTML	155	View/Open
Max-coloring of vertex-weighted graphs.pdf		396Kb	Adobe PDF	1	View/Open