Edge-partitions of sparse graphs and their applications to game coloring
PÊCHER, Arnaud
Laboratoire Bordelais de Recherche en Informatique [LaBRI]
Reformulations based algorithms for Combinatorial Optimization [Realopt]
Voir plus >
Laboratoire Bordelais de Recherche en Informatique [LaBRI]
Reformulations based algorithms for Combinatorial Optimization [Realopt]
PÊCHER, Arnaud
Laboratoire Bordelais de Recherche en Informatique [LaBRI]
Reformulations based algorithms for Combinatorial Optimization [Realopt]
< Réduire
Laboratoire Bordelais de Recherche en Informatique [LaBRI]
Reformulations based algorithms for Combinatorial Optimization [Realopt]
Langue
en
Autre document
Ce document a été publié dans
2009-03-04
Résumé en anglais
In this note, we prove that every graph with maximum average degree less than $\frac{32}{13}$ (resp. $\frac{30}{11}$, $\frac{32}{11}$, $\frac{70}{23}$) admits an edge-partition into a forest and a subgraph of maximum degree ...Lire la suite >
In this note, we prove that every graph with maximum average degree less than $\frac{32}{13}$ (resp. $\frac{30}{11}$, $\frac{32}{11}$, $\frac{70}{23}$) admits an edge-partition into a forest and a subgraph of maximum degree 1 (resp. 2, 3, 4). This implies that these graphs have game coloring number at most 5, 6, 7, 8, respectively.< Réduire
Origine
Importé de halUnités de recherche