Accéder aux actualités Evènements des groupes Liste des groupes publics
Evènement pour le groupe GT Graphes et Applications

 Date 2016-07-08  13:30-14:30 Titre List 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. Lieu Salle 178 Orateur Samia Kerdjoudj

Aucun document lié à cet événement.

Retour
Retour à l'index