Fractional chromatic number, maximum degree and girth
Nombre chromatique fractionnaire, degré maximum et maille
Résumé
We prove new lower bounds on the independence ratio of graphs of maximum degree ∆ ∈ {3, 4, 5} and girth g ∈ {6,. .. , 12}, notably 1/3 when (∆,g)=(4, 10) et 2/7 when (∆,g)=(5, 8). We also demonstrate that every graph of girth at least 7 and maximum degree ∆ has fractional chromatic number at most min (2∆+2 k−3 +k)/k over k∈N. In particular, the fractional chromatic number of a graph of girth 7 and maximum degree ∆ is at most (2∆+9)/5 when ∆ ∈ [3, 8], at most (∆+7)/3 when ∆ ∈ [8, 20], at most (2∆+23)/7 when ∆ ∈ [20, 48], and at most ∆/4 + 5 when ∆ ∈ [48, 112].
Nous démontrons de nouvelles bornes inférieures sur le quotient d'indépendance des graphes de degré maximum ∆ ∈ {3,4,5} et maille g ∈ {6,. .. , 12},
notamment 1/3 lorsque (∆,g)=(4, 10) et 2/7 lorsque (∆,g)=(5, 8). Nous démontrons également que tout graphe de maille au moins 7 et de degré maximum ∆ a nombre chromatique fractionnaire au plus min (2∆+2 k−3 +k)/k pour k∈N. En particulier, le nombre chromatique fractionnaire d'un graphe de maille 7 et degré maximum ∆ est au plus (2∆+9)/5 lorsque ∆ ∈ [3, 8], au plus (∆+7)/3 lorsque ∆ ∈ [8, 20], au plus (2∆+23)/7 lorsque ∆ ∈ [20, 48], et au plus ∆/4 + 5 lorsque ∆ ∈ [48, 112].
Fichier principal
pise19.pdf (468.63 Ko)
Télécharger le fichier
pise19 (1).pdf (467.28 Ko)
Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...