Chromatic roots and hamiltonian paths

被引：18
|
作者：
Thomassen, C [1 ]
机构：
[1] Tech Univ Denmark, Dept Math, DK-2800 Lyngby, Denmark
来源：
JOURNAL OF COMBINATORIAL THEORY SERIES B | 2000年 / 80卷 / 02期
关键词：
D O I：
10.1006/jctb.2000.1976
中图分类号：
O1 [数学];
学科分类号：
0701 ; 070101 ;
摘要：
We present a new connection between colorings and hamiltonian paths: If the chromatic polynomial of a graph has a noninteger root less than or equal to t(n) = 2/3 + 1/3 (3)root (26 + 6 root (33)) + 1/3 (3)root (26 - 6 root (33)) = 1.29559.... then the graph has no hamiltonian path. This result is best possible in the sense that ii becomes false if t(0) is replaced by any larger number. (C) 2000 Academic Press.
引用
收藏
页码：218 / 224
页数：7
相关论文
共 50 条
  • [21] Hamiltonian paths in distance graphs
    V. V. Utkin
    Mathematical Notes, 2015, 97 : 919 - 929
  • [22] On mutually independent hamiltonian paths
    Teng, YH
    Tan, JJM
    Ho, TY
    Hsu, LH
    APPLIED MATHEMATICS LETTERS, 2006, 19 (04) : 345 - 350
  • [23] Neighborhood Unuion and Hamiltonian Paths
    JIA Zhensheng Dept.of Mathematics Taiyuan Univ.of Technology Taiyuan
    JournalofSystemsScienceandSystemsEngineering, 1998, (02) : 3 - 5
  • [24] Hamiltonian orthogeodesic alternating paths
    Di Giacomo, Emilio
    Grilli, Luca
    Krug, Marcus
    Liotta, Giuseppe
    Rutter, Ignaz
    JOURNAL OF DISCRETE ALGORITHMS, 2012, 16 : 34 - 52
  • [25] On hamiltonian paths and a chain metric
    Burdyuk V.Y.
    Kakhichko A.A.
    Cybernetics and Systems Analysis, 2001, 37 (3) : 458 - 460
  • [26] Hamiltonian paths in Cayley graphs
    Pak, Igor
    Radoicic, Rados
    DISCRETE MATHEMATICS, 2009, 309 (17) : 5501 - 5508
  • [27] Chromatic layout number of paths and cycles
    Quadras, Jasintha
    Vasanthika, S.
    Journal of Combinatorial Mathematics and Combinatorial Computing, 2015, 92 : 167 - 174
  • [28] Independence, radius and hamiltonian paths
    Delavina, Ermelinda
    Pepper, Ryan
    Waller, Bill
    MATCH-COMMUNICATIONS IN MATHEMATICAL AND IN COMPUTER CHEMISTRY, 2007, 58 (02) : 481 - 510
  • [29] HAMILTONIAN PATHS IN ODD GRAPHS
    Bueno, Leticia R.
    Faria, Luerbio
    de Figueiredo, Celina M. H.
    da Fonseca, Guilherme D.
    APPLICABLE ANALYSIS AND DISCRETE MATHEMATICS, 2009, 3 (02) : 386 - 394
  • [30] Hamiltonian paths and cycles in hypertournaments
    Gutin, G
    Yeo, A
    JOURNAL OF GRAPH THEORY, 1997, 25 (04) : 277 - 286
12345