Evènement pour le groupe GT Graphes et Applications

Date 2016-07-08  13:30-14:30
TitreList star edge coloring of sparse graphs 
RésuméIn 2008, Liu and Deng introduced an edge version of star coloring. They defined a star-edge coloring of a graph $G$ as a proper edge coloring such that every $2$-colored connected subgraph of $G$ is a path of length at most $3$. This notion is intermediate between acyclic edge coloring, when every 2-colored subgraph must be only acyclic, and strong edge coloring, when every 2-colored connected subgraph has at most two vertices. For a graph $G$, let the list star chromatic index of $G$, $ch_s'(G)$, be the minimum $k$ such that for any $k$-uniform list assignment $L$ for the set of edges, $G$ has a star edge coloring from $L$. We proved already many bounds for the list star chromatic index of subcubic sparse graphs. In this talk, we will consider graphs with any maximum degree $Delta(G)$. No bound of the list star chromatic index is known for general graphs. In the case of sparse graphs it is possible to find bounds for the the list star chromatic index. We prove that if the maximum average degree of a graph $G$ is less than $frac{7}{3}$ (resp., $frac{5}{2}$,$frac{8}{3}$), then $ch'_s(G)leq 2Delta(G) -1$ (resp., $ch'_s(G)leq 2Delta(G)$, $ch'_s(G)leq 2Delta(G) +1$). Joint work with: André Raspaud.  
LieuSalle 178 
OrateurSamia Kerdjoudj 

Aucun document lié à cet événement.

Retour à l'index