Hostname: page-component-7b7567c8c-7pwfn Total loading time: 0 Render date: 2026-11-12T18:31:56.159Z 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: borgs@microsoft.com)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

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.

Information

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