umu.sePublications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Broken-cycle-free subgraphs and the log-concavity conjecture for chromatic polynomials
Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
2006 (English)In: Experimental Mathematics, ISSN 1058-6458, E-ISSN 1944-950X, Vol. 15, no 3, 343-353 p.Article in journal (Refereed) Published
Abstract [en]

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 epsilon(G), the average size of a broken-cycle-free subgraph of the graph G, whose behavior under edge deletion and contraction is studied.

Place, publisher, year, edition, pages
2006. Vol. 15, no 3, 343-353 p.
Keyword [en]
chromatic polynomial, log-concavity, subgraphs, bounds
National Category
Discrete Mathematics
Identifiers
URN: urn:nbn:se:umu:diva-52130DOI: 10.1080/10586458.2006.10128969ISI: 000241619800006OAI: oai:DiVA.org:umu-52130DiVA: diva2:497212
Available from: 2012-02-10 Created: 2012-02-10 Last updated: 2017-12-07Bibliographically approved

Open Access in DiVA

Broken-Cycle-Free Subgraphs and the Log-Concavity Conjecture for Chromatic Polynomials(371 kB)157 downloads
File information
File name FULLTEXT02.pdfFile size 371 kBChecksum SHA-512
e5ffbcbaa008a3e1091415056dc74bac1a22dc8b90ae18e1f96999a7f0fc99825be07874f023ea9ade642dbaf1088259cab6df97bc51c6c6d705f56e24b9beb7
Type fulltextMimetype application/pdf

Other links

Publisher's full text

Search in DiVA

By author/editor
Lundow, P. H.Markström, Klas
By organisation
Department of Mathematics and Mathematical Statistics
In the same journal
Experimental Mathematics
Discrete Mathematics

Search outside of DiVA

GoogleGoogle Scholar
Total: 157 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 80 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf