Bipartite powers of k-chordal graphs

Abstract : Let k be an integer and k ≥3. A graph G is k-chordal if G does not have an induced cycle of length greater than k. From the definition it is clear that 3-chordal graphs are precisely the class of chordal graphs. Duchet proved that, for every positive integer m, if Gm is chordal then so is Gm+2. Brandstädt et al. in [Andreas Brandstädt, Van Bang Le, and Thomas Szymczak. Duchet-type theorems for powers of HHD-free graphs. Discrete Mathematics, 177(1-3):9-16, 1997.] showed that if Gm is k-chordal, then so is Gm+2. Powering a bipartite graph does not preserve its bipartitedness. In order to preserve the bipartitedness of a bipartite graph while powering Chandran et al. introduced the notion of bipartite powering. This notion was introduced to aid their study of boxicity of chordal bipartite graphs. The m-th bipartite power G[m] of a bipartite graph G is the bipartite graph obtained from G by adding edges (u,v) where dG(u,v) is odd and less than or equal to m. Note that G[m] = G[m+1] for each odd m. In this paper we show that, given a bipartite graph G, if G is k-chordal then so is G[m], where k, m are positive integers with k≥4.
Type de document :
Article dans une revue
Discrete Mathematics and Theoretical Computer Science, DMTCS, 2013, Vol. 15 no. 2 (2), pp.49--58
Liste complète des métadonnées

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

https://hal.inria.fr/hal-00980750
Contributeur : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Soumis le : vendredi 18 avril 2014 - 16:43:29
Dernière modification le : jeudi 7 septembre 2017 - 01:03:48
Document(s) archivé(s) le : lundi 10 avril 2017 - 15:49:59

Fichier

2141-7874-1-PB.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00980750, version 1

Collections

Citation

Sunil Chandran, Rogers Mathew. Bipartite powers of k-chordal graphs. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2013, Vol. 15 no. 2 (2), pp.49--58. 〈hal-00980750〉

Partager

Métriques

Consultations de la notice

692

Téléchargements de fichiers

212