2018/03/31 by Fengming Dong, Jun Ge, Helin Gong +3
Engineering · Mathematics · #Advanced Combinatorial Mathematics #Chromatic polynomial #Chromatic scale #Conjecture #Critical graph #Graph #Graph factorization #Limits and Structures in Graph Theory #Order (exchange) #Spanning tree #Tutte polynomial #graph theory and CDMA systems #math.CO #msc:05C20 #msc:05C31
paper · pdf · doi:10.1002/jgt.22617
20 pages, 23 references. To appear in J. Graph Theory
arxiv created 2020/07/16 · openalex created_date 2020/07/23 · openalex publication_date 2020/07/31 · arxiv updated 2020/08/12 · openalex updated_date 2026/08/05
Abstract The chromatic polynomial of a graph of order can be expressed as , where is interpreted as the number of broken‐cycle‐free spanning subgraphs of with exactly components. The parameter is the mean size of a broken‐cycle‐free spanning subgraph of . In this article, we confirm and strengthen a conjecture proposed by Lundow and Markström in 2006 that holds for any connected graph of order which is neither the complete graph nor a tree of order . The most crucial step of our proof is to obtain the interpretation of all 's by the number of acyclic orientations of .