On the proper orientation number of bipartite graphs

Résumé : Une {\it orientation} d'un graphe~$G$ est un digraphe~$D$ obtenu á partir de $G$ en remplaçant chaque arête par exactement un des deux arcs possibles avec les mêmes extremités. Pour tout $v\in V(G)$, le {\it dégré entrant} de $v$ dans $D$, noté $d^-_D(v)$, est le nombre d'arcs de $D$ ayant $v$ pour tête. Une orientation~$D$ de $G$ est {\it propre} si~$d^-_D(u)\neq d^-_D(v)$, pour tout~$uv\in E(G)$. L'{\it indice d'orientation propre} d'un graphe $G$, noté~$\po(G)$, est le plus petit dégré maximum d'une orientation propre de $G$. Dans ce papier, nous prouvons que $\po(G) \leq \left\lfloor \left(\Delta(G) + \sqrt{\Delta(G)}\right)/2 \right\rfloor+ 1$ si~$G$ est un graphe biparti, et~$\po(G)\leq 4$ si~$G$ est un arbre. Il est connu que~$\po(G)\leq \Delta(G)$, pour tout graphe~$G$. En revancche, nous prouvons que décider si~$\po(G)\leq \Delta(G)-1$ est déjá un probléme $\NP$-complet. Nous montrons aussi qu'il est $\NP$-complet de décider si~$\po(G)\leq 2$ pour un graphe planaire subcubique~$G$. Enfin nous montrons qu'il est $\NP$-complet de décider si $\po(G)\leq 3$ pour un graphe planaire biparti~$G$ de dégré maximum~5.
Type de document :
Rapport
[Research Report] RR-8492, INRIA. 2014, pp.23
Liste complète des métadonnées

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

https://hal.inria.fr/hal-00957453
Contributeur : Julio Araujo <>
Soumis le : lundi 10 mars 2014 - 19:56:42
Dernière modification le : mercredi 4 janvier 2017 - 16:19:41
Document(s) archivé(s) le : mardi 10 juin 2014 - 12:10:53

Fichier

RR-8492.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00957453, version 1

Collections

Citation

Julio Araujo, Nathann Cohen, Susanna F. De Rezende, Frédéric Havet, Phablo Moura. On the proper orientation number of bipartite graphs. [Research Report] RR-8492, INRIA. 2014, pp.23. 〈hal-00957453〉

Partager

Métriques

Consultations de
la notice

370

Téléchargements du document

228