On a 1, 2 Conjecture

Abstract : Let us assign positive integers to the edges and vertices of a simple graph G. As a result we obtain a vertex-colouring of G with integers, where a vertex colour is simply a sum of the weight assigned to the vertex itself and the weights of its incident edges. Can we obtain a proper colouring using only weights 1 and 2 for an arbitrary G? We give a positive answer when G is a 3-colourable, complete or 4-regular graph. We also show that it is enough to C use weights from 1 to 11, as well as from 1 to 11 [chi(G)/2] + 1, for an arbitrary graph G.
Type de document :
Article dans une revue
Discrete Mathematics and Theoretical Computer Science, DMTCS, 2010, 12 (1), pp.101-108
Liste complète des métadonnées

Littérature citée [11 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00990444
Contributeur : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Soumis le : mardi 13 mai 2014 - 15:37:15
Dernière modification le : jeudi 16 août 2018 - 17:02:02
Document(s) archivé(s) le : lundi 10 avril 2017 - 22:25:53

Fichier

948-4947-1-PB.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00990444, version 1

Collections

Citation

Jakub Przybylo, Mariusz Woźniak. On a 1, 2 Conjecture. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2010, 12 (1), pp.101-108. 〈hal-00990444〉

Partager

Métriques

Consultations de la notice

77

Téléchargements de fichiers

377