Some new bounds for the maximum number of vertex colorings of a (v,e)-graph

✍ Scribed by Byer, Owen D.

• Publisher: John Wiley and Sons
• Year: 1998
• Tongue: English
• Weight: 126 KB
• Volume: 28
• Category: Article
• ISSN: 0364-9024
• DOI: 10.1002/(sici)1097-0118(199807)28:3<115::aid-jgt1>3.0.co;2-n

✦ Synopsis

Let f (v, e, λ) denote the maximum number of proper vertex colorings of a graph with v vertices and e edges in λ colors. In this paper we present some new upper bounds for f (v, e, λ). In particular, a new notion of pseudoproper colorings of a graph is given, which allows us to significantly improve the upper bounds for f (v, e, 3) given by Lazebnik and Liu in the case where e > v 2 /4.