Chromatic roots at 2 and the Beraha number B10

被引：0

作者：

Harvey, Daniel J. ^{[1
]}

Royle, Gordon F. ^{[1
]}

机构：

[1] Univ Western Australia, Math & Stat, Nedlands, WA 6009, Australia

来源：

JOURNAL OF GRAPH THEORY | 2020年 / 95卷 / 03期

基金：

澳大利亚研究理事会;

关键词：

Beraha number; chromatic polynomial; chromatic root; recursive family; GRAPH;

D O I：

10.1002/jgt.22566

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

By the construction of suitable graphs and the determination of their chromatic polynomials, we resolve two open questions concerning real chromatic roots. First we exhibit graphs for which the Beraha number B10=(5+5)/2 is a chromatic root. As it was previously known that no other noninteger Beraha number is a chromatic root, this completes the determination of precisely which Beraha numbers can be chromatic roots. Next we construct an infinite family of 3-connected graphs such that for any k >= 1, there is a member of the family with q=2 as a chromatic root of multiplicity at least k. The former resolves a question of Salas and Sokal and the latter a question of Dong and Koh.

引用

页码：445 / 456

页数：12

共 9 条

[1]

Biggs N, 1972, J COMBIN THEORY B, V12, P123, DOI [10.1016/0095-8956(72)90016-0, DOI 10.1016/0095-8956(72)90016-0, 10.1016/0095-8956, DOI 10.1016/0095-8956]

[2] The 3-connectivity of a graph and the multiplicity of zero "2" of its chromatic polynomial [J].

Dong, F. M. ;

Koh, K. M. .

JOURNAL OF GRAPH THEORY, 2012, 70 (03) :262-283

[3]

Jackson B., 1993, Combin. Probab. Comput, V2, P325, DOI [10.1017/S0963548300000705, DOI 10.1017/S0963548300000705]

[4] Recursively constructible families of graphs [J].

Noy, M ;

Ribó, A .

ADVANCES IN APPLIED MATHEMATICS, 2004, 32 (1-2) :350-363

[5] Density of Chromatic Roots in Minor-Closed Graph Families [J].

Perrett, Thomas J. ;

Thomassen, Carsten .

COMBINATORICS PROBABILITY & COMPUTING, 2018, 27 (06) :988-998

[6] Transfer matrices and partition-function zeros for antiferromagnetic potts models. I. General theory and square-lattice chromatic polynomial [J].

Salas, J ;

Sokal, AD .

JOURNAL OF STATISTICAL PHYSICS, 2001, 104 (3-4) :609-699

[7]

Sokal A.D., 2005, Surveys Combinatorics, V0, P173, DOI [DOI 10.1017/CB09780511734885.009, 10.1017/CBO9780511734885.009]

[8]

Thomassen C., 1997, Combinatorics, Probability and Computing, V6, P497, DOI 10.1017/S0963548397003131

[9]

Tutte W.T., 1970, J COMBINATORIAL THEO, V9, P289, DOI 10.1016/S0021-9800(70)80067-9

← 1 →