Bispindles in strongly connected digraphs with large chromatic number - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Article Dans Une Revue The Electronic Journal of Combinatorics Année : 2018

Bispindles in strongly connected digraphs with large chromatic number

Résumé

A (k1 + k2)-bispindle is the union of k1 (x, y)-dipaths and k2 (y, x)-dipaths, all these dipaths being pairwise internally disjoint. Recently, Cohen et al. showed that for every (1, 1)- bispindle B, there exists an integer k such that every strongly connected digraph with chromatic number greater than k contains a subdivision of B. We investigate generalizations of this result by first showing constructions of strongly connected digraphs with large chromatic number without any (3,0)- bispindle or (2,2)-bispindle. We then consider (2,1)-bispindles. Let B(k1,k2;k3) denote the (2, 1)-bispindle formed by three internally disjoint dipaths between two vertices x, y, two (x, y)-dipaths, one of length k1 and the other of length k2, and one (y,x)-dipath of length k3. We conjecture that for any positive integers k1,k2,k3, there is an integer g(k1,k2,k3) such that every strongly connected digraph with chromatic number greater than g(k1, k2, k3) contains a subdivision of B(k1, k2; k3). As evidence, we prove this conjecture for k2 = 1 (and k1, k3 arbitrary).
Fichier principal
Vignette du fichier
6922-24594-2-PB.pdf (322.58 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-01810706 , version 1 (08-06-2018)

Identifiants

Citer

Nathann Cohen, Frédéric Havet, William Lochet, Raul Lopes. Bispindles in strongly connected digraphs with large chromatic number. The Electronic Journal of Combinatorics, 2018, ⟨10.37236/6922⟩. ⟨hal-01810706⟩
183 Consultations
97 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More