Hostname: page-component-cd9895bd7-gvvz8 Total loading time: 0 Render date: 2024-12-25T19:13:07.897Z Has data issue: false hasContentIssue false
  • English
  • Français

Absence of Zeros for the Chromatic Polynomial on Bounded Degree Graphs

Published online by Cambridge University Press:  03 January 2006

CHRISTIAN BORGS
CHRISTIAN BORGS
Affiliation:
Microsoft Research, One Microsoft Way, Redmond WA 98052, USA (e-mail: [email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

In this paper, I give a short proof of a recent result by Sokal, showing that all zeros of the chromatic polynomial $P_G(q)$ of a finite graph $G$ of maximal degree $D$ lie in the disk $|q|< K D$, where $K$ is a constant that is strictly smaller than 8.

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 15 , Issue 1-2 , January 2006 , pp. 63 - 74
Copyright
2006 Cambridge University Press

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)