05C15 — 1 articles found.

Polynômes chromatiques de certains graphes de la vie réelle

C. R. Math. Rep. Acad. Sci. Canada Vol. 41 (1) 2019, pp. 7-19
Vol.41 (1) 2019
Jasbir S. Chahal; Omar Khadir Details
(Received: 2019-05-05 , Revised: 2019-06-17 )
(Received: 2019-05-05 , Revised: 2019-06-17 )

Jasbir S. Chahal,Department de Mathematiques, Universite de Brigham Young, Provo, UT 84602, USA; email: asbir@math.byu.edu

Omar Khadir,Laboratoire de Mathematiques, cryptographie, mecanique et analyse numerique, Fstm., Universite Hassan II de Casablanca, Maroc; email:
khadir@hotmail.com

Abstract/Résumé:

La conjecture des quatre couleurs affirme que toute carte géographique à bords continus nécessite au plus quatre couleurs pour être proprement colorée. Certains pays comme le Canada exigent en réalité seulement trois couleurs alors que d’autres, comme le Maroc, nécessitent eux quatre couleurs, trois ne suffisant pas. Soit \(k=k(X)\) le plus petit nombre de couleurs nécessaires au coloriage de la carte d’un pays. Aucun calcul n’a été fait pour déterminer de combien de manières \(X\) peut-il être coloré avec les \(k\) couleurs même pour un seul pays pour lequel le problème n’est pas trivial. Dans ce travail, nous le réalisons pour deux pays : le Canada et le Maroc. Nous décrivons tous les outils mathématiques dont nous aurons besoin.

The four color conjecture states that any contiguous geographical entity needs at most four colors to color it properly. Some countries like Canada need actually only three colors whereas for others like Morocco three won’t suffice. Let \(k=k(X)\) be the least number of colors that suffice to color a country \(X\). Someone has yet to compute in how many ways \(X\) can be colored with \(k\) colors, even for a single country \(X\) for which the problem is non-trivial. In this paper, we do it for the two countries Canada and Morocco. We provide all the mathematical tools that are necessary.

Keywords:

AMS Subject Classification: Coloring of graphs and hypergraphs, 05C15, 05C31

PDF(click to download): Polynômes chromatiques de certains graphes de la vie réelle