Mathematica Eterna
Libre accès
ISSN: 1314-3344
ISSN: 1314-3344
Mohammed Hussein
Le graphe de Gallai et donc le graphe anti-Gallai d'un graphe G ont les périmètres de G comme sommets. 2 arêtes de G sont adjacentes dans le graphe de Gallai de G si elles sont incidentes mais ne couvrent pas un triangle dans G ; elles sont adjacentes dans le graphe anti-Gallai de G si elles couvrent un triangle dans G. Dans cet article, nous montrons : Le théorème des quatre couleurs est souvent équivalent explicite en termes de graphes anti-Gallai ; les questions de la gamme de cercles intérieurs et donc de la gamme chromatique d'un graphe de Gallai sont NP-completes. De plus, nous discutons de la relation des graphes de Gallai à la théorie des graphes parfaits. Une caractérisation des graphes de Gallai et des graphes anti-Gallai est également donnée [1].