Broken-Cycle-Free Subgraphs and the Log-Concavity Conjecture for Chromatic Polynomials

This paper concerns the coefficients of the chromatic polynomial of a graph. We first report on a computational verification of the strict log-concavity conjecture for chromatic polynomials for all graphs on at most 11 vertices, as well as for certain cubic graphs. In the second part of the paper we...

Full description

Saved in:
Bibliographic Details
Published in:Experimental mathematics 2006-01, Vol.15 (3), p.343-353
Main Authors: Lundow, P. H., Markström, K.
Format: Article
Language:English
Subjects:
05C15
bounds
Chromatic polynomial
log-concavity
Primary 05C15
subgraphs
Citations: Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
cited_by cdi_FETCH-LOGICAL-c491t-4167b7f47ad83b76109771785ac79dea5d80030c13ce23cdc7d9670c62efe4143
cites
container_end_page 353
container_issue 3
container_start_page 343
container_title Experimental mathematics
container_volume 15
creator Lundow, P. H.
Markström, K.
description This paper concerns the coefficients of the chromatic polynomial of a graph. We first report on a computational verification of the strict log-concavity conjecture for chromatic polynomials for all graphs on at most 11 vertices, as well as for certain cubic graphs. In the second part of the paper we give a number of conjectures and theorems regarding the behavior of the coefficients of the chromatic polynomial, in part motivated by our computations. Here our focus is on ε(G), the average size of a broken-cyclefree subgraph of the graph G, whose behavior under edge deletion and contraction is studied.
doi_str_mv 10.1080/10586458.2006.10128969
format article
fullrecord <record><control><sourceid>swepub_proje</sourceid><recordid>TN_cdi_projecteuclid_primary_oai_CULeuclid_euclid_em_1175789763</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><sourcerecordid>oai_DiVA_org_kth_16095</sourcerecordid><originalsourceid>FETCH-LOGICAL-c491t-4167b7f47ad83b76109771785ac79dea5d80030c13ce23cdc7d9670c62efe4143</originalsourceid><addsrcrecordid>eNqNkVtr20AQhUVJoE6av1D0Ayp3RtrrU3HV3MDQQi70bVmvVvbaktaspAT9-65xHOhT-3SG4TsHZk6SfEaYIwj4ikAFI1TMcwAWV5gLyeSHZIaSkExS-H0W5whlB-pjctH3WwAkVIpZ8vw9-J3tsnIyjc1ugrXpw7haB73f9KnuqnTY2HTp11npO6Nf3DClcdpaM4zBprUPabkJvtWDM-kv30ydb51u-k_JeR3FXr3pZfJ0c_1Y3mXLn7f35WKZGSJxyAgyvuI14boSxYozBMk5ckG14bKymlYCoACDhbF5YSrDK8k4GJbb2hIkxWXy5Zjbv9r9uFL74FodJuW1Uz_c80L5sFZjOyqaYwH_h--GjUIGkkb82xHfB3842Y6mcdVfrvJp-bY9SasQOeVCclbEBHZMMMH3fbD1uxlBHdpTp_bUoT11ai8aF0ej6-KTW_3qQ1OpQU-ND3XQnXG9Kv6R8QepeaMR</addsrcrecordid><sourcetype>Open Access Repository</sourcetype><iscdi>true</iscdi><recordtype>article</recordtype></control><display><type>article</type><title>Broken-Cycle-Free Subgraphs and the Log-Concavity Conjecture for Chromatic Polynomials</title><source>Taylor and Francis:Jisc Collections:Taylor and Francis Read and Publish Agreement 2024-2025:Science and Technology Collection (Reading list)</source><source>Project Euclid Complete</source><creator>Lundow, P. H. ; Markström, K.</creator><creatorcontrib>Lundow, P. H. ; Markström, K.</creatorcontrib><description>This paper concerns the coefficients of the chromatic polynomial of a graph. We first report on a computational verification of the strict log-concavity conjecture for chromatic polynomials for all graphs on at most 11 vertices, as well as for certain cubic graphs. In the second part of the paper we give a number of conjectures and theorems regarding the behavior of the coefficients of the chromatic polynomial, in part motivated by our computations. Here our focus is on ε(G), the average size of a broken-cyclefree subgraph of the graph G, whose behavior under edge deletion and contraction is studied.</description><identifier>ISSN: 1058-6458</identifier><identifier>ISSN: 1944-950X</identifier><identifier>EISSN: 1944-950X</identifier><identifier>DOI: 10.1080/10586458.2006.10128969</identifier><language>eng</language><publisher>A.K. Peters</publisher><subject>05C15 ; bounds ; Chromatic polynomial ; log-concavity ; Primary 05C15 ; subgraphs</subject><ispartof>Experimental mathematics, 2006-01, Vol.15 (3), p.343-353</ispartof><rights>Copyright Taylor &amp; Francis Group, LLC 2006</rights><rights>Copyright 2006 A K Peters, Ltd.</rights><lds50>peer_reviewed</lds50><oa>free_for_read</oa><woscitedreferencessubscribed>false</woscitedreferencessubscribed><citedby>FETCH-LOGICAL-c491t-4167b7f47ad83b76109771785ac79dea5d80030c13ce23cdc7d9670c62efe4143</citedby></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><linktopdf>$$Uhttps://projecteuclid.org/accountAjax/Download?downloadType=journal%20article&amp;urlId=10.1080/10586458.2006.10128969&amp;isResultClick=True$$EPDF$$P50$$Gprojecteuclid$$H</linktopdf><linktohtml>$$Uhttp://projecteuclid.org/euclid.em/1175789763$$EHTML$$P50$$Gprojecteuclid$$H</linktohtml><link.rule.ids>230,314,776,780,881,921,4010,27900,27901,27902,79752,79760</link.rule.ids><backlink>$$Uhttps://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-16095$$DView record from Swedish Publication Index$$Hfree_for_read</backlink><backlink>$$Uhttps://urn.kb.se/resolve?urn=urn:nbn:se:umu:diva-52130$$DView record from Swedish Publication Index$$Hfree_for_read</backlink></links><search><creatorcontrib>Lundow, P. H.</creatorcontrib><creatorcontrib>Markström, K.</creatorcontrib><title>Broken-Cycle-Free Subgraphs and the Log-Concavity Conjecture for Chromatic Polynomials</title><title>Experimental mathematics</title><description>This paper concerns the coefficients of the chromatic polynomial of a graph. We first report on a computational verification of the strict log-concavity conjecture for chromatic polynomials for all graphs on at most 11 vertices, as well as for certain cubic graphs. In the second part of the paper we give a number of conjectures and theorems regarding the behavior of the coefficients of the chromatic polynomial, in part motivated by our computations. Here our focus is on ε(G), the average size of a broken-cyclefree subgraph of the graph G, whose behavior under edge deletion and contraction is studied.</description><subject>05C15</subject><subject>bounds</subject><subject>Chromatic polynomial</subject><subject>log-concavity</subject><subject>Primary 05C15</subject><subject>subgraphs</subject><issn>1058-6458</issn><issn>1944-950X</issn><issn>1944-950X</issn><fulltext>true</fulltext><rsrctype>article</rsrctype><creationdate>2006</creationdate><recordtype>article</recordtype><recordid>eNqNkVtr20AQhUVJoE6av1D0Ayp3RtrrU3HV3MDQQi70bVmvVvbaktaspAT9-65xHOhT-3SG4TsHZk6SfEaYIwj4ikAFI1TMcwAWV5gLyeSHZIaSkExS-H0W5whlB-pjctH3WwAkVIpZ8vw9-J3tsnIyjc1ugrXpw7haB73f9KnuqnTY2HTp11npO6Nf3DClcdpaM4zBprUPabkJvtWDM-kv30ydb51u-k_JeR3FXr3pZfJ0c_1Y3mXLn7f35WKZGSJxyAgyvuI14boSxYozBMk5ckG14bKymlYCoACDhbF5YSrDK8k4GJbb2hIkxWXy5Zjbv9r9uFL74FodJuW1Uz_c80L5sFZjOyqaYwH_h--GjUIGkkb82xHfB3842Y6mcdVfrvJp-bY9SasQOeVCclbEBHZMMMH3fbD1uxlBHdpTp_bUoT11ai8aF0ej6-KTW_3qQ1OpQU-ND3XQnXG9Kv6R8QepeaMR</recordid><startdate>20060101</startdate><enddate>20060101</enddate><creator>Lundow, P. H.</creator><creator>Markström, K.</creator><general>A.K. Peters</general><general>A K Peters, Ltd</general><scope>AAYXX</scope><scope>CITATION</scope><scope>ADTPV</scope><scope>AOWAS</scope><scope>D8V</scope><scope>ADHXS</scope><scope>D8T</scope><scope>D93</scope><scope>ZZAVC</scope></search><sort><creationdate>20060101</creationdate><title>Broken-Cycle-Free Subgraphs and the Log-Concavity Conjecture for Chromatic Polynomials</title><author>Lundow, P. H. ; Markström, K.</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-c491t-4167b7f47ad83b76109771785ac79dea5d80030c13ce23cdc7d9670c62efe4143</frbrgroupid><rsrctype>articles</rsrctype><prefilter>articles</prefilter><language>eng</language><creationdate>2006</creationdate><topic>05C15</topic><topic>bounds</topic><topic>Chromatic polynomial</topic><topic>log-concavity</topic><topic>Primary 05C15</topic><topic>subgraphs</topic><toplevel>peer_reviewed</toplevel><toplevel>online_resources</toplevel><creatorcontrib>Lundow, P. H.</creatorcontrib><creatorcontrib>Markström, K.</creatorcontrib><collection>CrossRef</collection><collection>SwePub</collection><collection>SwePub Articles</collection><collection>SWEPUB Kungliga Tekniska Högskolan</collection><collection>SWEPUB Umeå universitet full text</collection><collection>SWEPUB Freely available online</collection><collection>SWEPUB Umeå universitet</collection><collection>SwePub Articles full text</collection><jtitle>Experimental mathematics</jtitle></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext</fulltext></delivery><addata><au>Lundow, P. H.</au><au>Markström, K.</au><format>journal</format><genre>article</genre><ristype>JOUR</ristype><atitle>Broken-Cycle-Free Subgraphs and the Log-Concavity Conjecture for Chromatic Polynomials</atitle><jtitle>Experimental mathematics</jtitle><date>2006-01-01</date><risdate>2006</risdate><volume>15</volume><issue>3</issue><spage>343</spage><epage>353</epage><pages>343-353</pages><issn>1058-6458</issn><issn>1944-950X</issn><eissn>1944-950X</eissn><abstract>This paper concerns the coefficients of the chromatic polynomial of a graph. We first report on a computational verification of the strict log-concavity conjecture for chromatic polynomials for all graphs on at most 11 vertices, as well as for certain cubic graphs. In the second part of the paper we give a number of conjectures and theorems regarding the behavior of the coefficients of the chromatic polynomial, in part motivated by our computations. Here our focus is on ε(G), the average size of a broken-cyclefree subgraph of the graph G, whose behavior under edge deletion and contraction is studied.</abstract><pub>A.K. Peters</pub><doi>10.1080/10586458.2006.10128969</doi><tpages>11</tpages><oa>free_for_read</oa></addata></record>
fulltext fulltext
identifier ISSN: 1058-6458
ispartof Experimental mathematics, 2006-01, Vol.15 (3), p.343-353
issn 1058-6458
1944-950X
1944-950X
language eng
recordid cdi_projecteuclid_primary_oai_CULeuclid_euclid_em_1175789763
source Taylor and Francis:Jisc Collections:Taylor and Francis Read and Publish Agreement 2024-2025:Science and Technology Collection (Reading list); Project Euclid Complete
subjects 05C15
bounds
Chromatic polynomial
log-concavity
Primary 05C15
subgraphs
title Broken-Cycle-Free Subgraphs and the Log-Concavity Conjecture for Chromatic Polynomials
url http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2025-02-23T15%3A38%3A31IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-swepub_proje&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.genre=article&rft.atitle=Broken-Cycle-Free%20Subgraphs%20and%20the%20Log-Concavity%20Conjecture%20for%20Chromatic%20Polynomials&rft.jtitle=Experimental%20mathematics&rft.au=Lundow,%20P.%20H.&rft.date=2006-01-01&rft.volume=15&rft.issue=3&rft.spage=343&rft.epage=353&rft.pages=343-353&rft.issn=1058-6458&rft.eissn=1944-950X&rft_id=info:doi/10.1080/10586458.2006.10128969&rft_dat=%3Cswepub_proje%3Eoai_DiVA_org_kth_16095%3C/swepub_proje%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-c491t-4167b7f47ad83b76109771785ac79dea5d80030c13ce23cdc7d9670c62efe4143%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_id=info:pmid/&rfr_iscdi=true