|
MASCOTTE no longer exists => visit the new project-team
Seminaire MASCOTTEb-coloring tight graphs
par Leonardo Sampaio
| Date : | 05/10/10 | | Time : | 10:30 | | Location : | Euler Violet |
<pre>A proper coloring c of a graph G = (V, E) is a b-coloring if in every
color class there is a vertex whose neighborhood intersects every other
color classes.
The b-chromatic number of G, denoted chi_b(G), is the greatest integer
k such that G admits a b-coloring with k colors.
Given a proper coloring of a graph, one strategy to reduce the number of
colors is to move all the vertices in one color class to others.
The b-colorings are colorings that cannot be improved in that way, and
chi_b(G) can be seen as the worst-case behaviour of the previous strategy.
Determining the b-chromatic number of a graph G was shown to be NP-hard
even for a connected bipartite graph.
In this talk we determine the complexity of the problem when restricted
to other graph classes.
In particular, we consider the problem of deciding if chi_b(G) is equal
to the upper bound m(G), which is the is the largest integer m such that
G has at least m vertices of degree at least m-1.
We define tight graphs, which are graphs with exactly m(G) vertices of
degree m(G) - 1, and we show that the problem of determining if
chi_b(G) = m(G) is NP-complete even if G is a tight chordal graph.
We give polynomial algorithms for tight graphs that are complement of
bipartite graphs, P_4-sparse graphs and block graphs.<br /><br />Joint work with F. Havet and C. Linhares-Sales<br /></pre>
Page des séminaires
|
