More connections between the matching polynomial and the chromatic polynomial
The connection between the matching polynomial and the chromatic polynomial for triangle-free graphs was revealed in the work of Farrell and Whitehead. We extend this result to all graph by mirroring the corresponding result of Godsil and Gutman for the acyclic polynomial and the characteristic poly...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Taylor & Francis Group
2019-12-01
|
| Series: | AKCE International Journal of Graphs and Combinatorics |
| Online Access: | http://www.sciencedirect.com/science/article/pii/S0972860017301226 |
| _version_ | 1811225570583773184 |
|---|---|
| author | Beatriz Carely Luna-Olivera Criel Merino Marcelino Ramírez-Ibáñez |
| author_facet | Beatriz Carely Luna-Olivera Criel Merino Marcelino Ramírez-Ibáñez |
| author_sort | Beatriz Carely Luna-Olivera |
| collection | DOAJ |
| description | The connection between the matching polynomial and the chromatic polynomial for triangle-free graphs was revealed in the work of Farrell and Whitehead. We extend this result to all graph by mirroring the corresponding result of Godsil and Gutman for the acyclic polynomial and the characteristic polynomial. We also reintroduce the clique polynomial of Farrell as an evaluation of the U-polynomial of Noble and Welsh, which also happens to contain the matching and chromatic polynomials. Keywords: Matching polynomial, Chromatic polynomial, F-polynomial, U-polynomial |
| first_indexed | 2024-04-12T09:09:33Z |
| format | Article |
| id | doaj.art-a5f54c314203467cb32d04ccc36f5b5b |
| institution | Directory Open Access Journal |
| issn | 0972-8600 |
| language | English |
| last_indexed | 2024-04-12T09:09:33Z |
| publishDate | 2019-12-01 |
| publisher | Taylor & Francis Group |
| record_format | Article |
| series | AKCE International Journal of Graphs and Combinatorics |
| spelling | doaj.art-a5f54c314203467cb32d04ccc36f5b5b2022-12-22T03:39:00ZengTaylor & Francis GroupAKCE International Journal of Graphs and Combinatorics0972-86002019-12-01163319323More connections between the matching polynomial and the chromatic polynomialBeatriz Carely Luna-Olivera0Criel Merino1Marcelino Ramírez-Ibáñez2Instituto de Agroingeniería, Universidad del Papaloapan, Av. Ferrocarril S/N Loma Bonita, 68400, Oaxaca, MexicoInstituto de Matemáticas, Universidad Nacional Autónoma de México, Área de la Investigación científica, Circuito Exterior, C.U., Coyoacán, 04510, México D.F., MexicoInstituto de Agroingeniería, Universidad del Papaloapan, Av. Ferrocarril S/N Loma Bonita, 68400, Oaxaca, Mexico; Corresponding author.The connection between the matching polynomial and the chromatic polynomial for triangle-free graphs was revealed in the work of Farrell and Whitehead. We extend this result to all graph by mirroring the corresponding result of Godsil and Gutman for the acyclic polynomial and the characteristic polynomial. We also reintroduce the clique polynomial of Farrell as an evaluation of the U-polynomial of Noble and Welsh, which also happens to contain the matching and chromatic polynomials. Keywords: Matching polynomial, Chromatic polynomial, F-polynomial, U-polynomialhttp://www.sciencedirect.com/science/article/pii/S0972860017301226 |
| spellingShingle | Beatriz Carely Luna-Olivera Criel Merino Marcelino Ramírez-Ibáñez More connections between the matching polynomial and the chromatic polynomial AKCE International Journal of Graphs and Combinatorics |
| title | More connections between the matching polynomial and the chromatic polynomial |
| title_full | More connections between the matching polynomial and the chromatic polynomial |
| title_fullStr | More connections between the matching polynomial and the chromatic polynomial |
| title_full_unstemmed | More connections between the matching polynomial and the chromatic polynomial |
| title_short | More connections between the matching polynomial and the chromatic polynomial |
| title_sort | more connections between the matching polynomial and the chromatic polynomial |
| url | http://www.sciencedirect.com/science/article/pii/S0972860017301226 |
| work_keys_str_mv | AT beatrizcarelylunaolivera moreconnectionsbetweenthematchingpolynomialandthechromaticpolynomial AT crielmerino moreconnectionsbetweenthematchingpolynomialandthechromaticpolynomial AT marcelinoramirezibanez moreconnectionsbetweenthematchingpolynomialandthechromaticpolynomial |