Skip to main contentSkip to search
Episciences
Open Access Journals
Sign in(new window)
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Sign in(new window)
Articles & Issues
All articlesAll accepted articlesAll volumesLast volumeSectionsSpecial issuesAuthors
About
The journalIndexing
Boards
Publish
For authorsEthical charter
Submit
Discrete Mathematics & Theoretical Computer Science logo
Contact
|
Credits
eISSN 1365-8050
|
RSS
|
Atom
Episciences
Documentation
|
Acknowledgements
|
Publishing policy
Accessibility: non-compliant
|
Legal mentions
|
Privacy statement
|
Terms of use
  1. Home > Articles & Issues >
  2. Articles >
  3. On the degree-chroma ...
Conference paper

On the degree-chromatic polynomial of a tree

Diego Cifuentes (1)
(1) Departamento de Matematicas [Univ de los Andes Colombia]
Download article
Open on HAL
Imported on
January 31, 2017
Published on
December 31, 2011
Last modified on
March 31, 2025
Volume
DMTCS Proceedings vol. AR, 24th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2012)
Proceedings
DOI
10.46298/dmtcs.3020
License
https://about.hal.science/hal-authorisation-v1
Indicators
662
Views
717
Downloads

On the degree-chromatic polynomial of a tree

Diego Cifuentes (1)
(1) Departamento de Matematicas [Univ de los Andes Colombia]
Abstract
English
The degree chromatic polynomial $P_m(G,k)$ of a graph $G$ counts the number of $k$ -colorings in which no vertex has m adjacent vertices of its same color. We prove Humpert and Martin's conjecture on the leading terms of the degree chromatic polynomial of a tree.
French
Le polynôme degré chromatique $P_m(G,k)$ d'un graphe $G$ compte le nombre de $k$-colorations dans lesquelles aucun sommet n'a m sommets adjacents de sa même couleur. On démontre la conjecture de Humpert et Martin sur les coefficients principaux du polynôme degré chromatique d'un arbre.
Keywords
  • [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]
  • chromatic polynomial
  • graph coloring
  • tree
Preview
Loading PDF preview...