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]
See more >
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]
< Reduce
Laboratoire Bordelais de Recherche en Informatique [LaBRI]
Reformulations based algorithms for Combinatorial Optimization [Realopt]
Language
en
Autre document
This item was published in
2009-03-04
English Abstract
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 ...Read more >
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.Read less <
Origin
Hal imported