On the performance guarantee of First Fit for sum coloring

作者：

Highlights：

• A thorough study of the approximation ratio for the natural algorithm First Fit.

• A study of sum coloring of graphs, of vertices or edges.

• A tight analysis of (k+1)-claw free graphs, with new types of examples.

• A tight analysis for important subclasses of via linear programs.

• A tight analysis for edge coloring and a tight analysis for unit interval graphs.

摘要

•A thorough study of the approximation ratio for the natural algorithm First Fit.•A study of sum coloring of graphs, of vertices or edges.•A tight analysis of (k+1)-claw free graphs, with new types of examples.•A tight analysis for important subclasses of via linear programs.•A tight analysis for edge coloring and a tight analysis for unit interval graphs.

论文关键词：Graph coloring,Chromatic sum number of graphs,First Fit,Approximation algorithm

论文评审过程：Received 25 August 2016, Revised 25 September 2017, Accepted 8 August 2018, Available online 21 September 2018, Version of Record 10 October 2018.

论文官网地址：https://doi.org/10.1016/j.jcss.2018.08.002