排序方式: 共有4条查询结果,搜索用时 0 毫秒
1
1.
An adjacent vertex-distinguishing edge coloring, or avd-coloring, of a graph G is a proper edge coloring of G such that no pair of adjacent vertices meets the same set of colors. Let $\operatorname {mad}(G)$ and Δ(G) denote the maximum average degree and the maximum degree of a graph G, respectively. In this paper, we prove that every graph G with Δ(G)≥5 and $\operatorname{mad}(G) < 3-\frac {2}{\Delta}$ can be avd-colored with Δ(G)+1 colors. This completes a result of Wang and Wang (J. Comb. Optim. 19:471–485, 2010). 相似文献
2.
Journal of Combinatorial Optimization - Given a graph G and a list assignment L(v) for each vertex of v of G, a proper L-list-coloring of G is a function that maps every vertex to a color in L(v)... 相似文献
3.
Clément Charpentier Mickaël Montassier André Raspaud 《Journal of Combinatorial Optimization》2013,25(4):646-660
Let p and q be positive integers. An L(p,q)-labeling of a graph G with a span s is a labeling of its vertices by integers between 0 and s such that adjacent vertices of G are labeled using colors at least p apart, and vertices having a common neighbor are labeled using colors at least q apart. We denote by λ p,q (G) the least integer k such that G has an L(p,q)-labeling with span k. The maximum average degree of a graph G, denoted by $\operatorname {Mad}(G)$ , is the maximum among the average degrees of its subgraphs (i.e. $\operatorname {Mad}(G) = \max\{\frac{2|E(H)|}{|V(H)|} ; H \subseteq G \}$ ). We consider graphs G with $\operatorname {Mad}(G) < \frac{10}{3}$ , 3 and $\frac{14}{5}$ . These sets of graphs contain planar graphs with girth 5, 6 and 7 respectively. We prove in this paper that every graph G with maximum average degree m and maximum degree Δ has: λ p,q (G)≤(2q?1)Δ+6p+10q?8 if $m < \frac{10}{3}$ and p≥2q. λ p,q (G)≤(2q?1)Δ+4p+14q?9 if $m < \frac{10}{3}$ and 2q>p. λ p,q (G)≤(2q?1)Δ+4p+6q?5 if m<3. λ p,q (G)≤(2q?1)Δ+4p+4q?4 if $m < \frac{14}{5}$ . We give also some refined bounds for specific values of p, q, or Δ. By the way we improve results of Lih and Wang (SIAM J. Discrete Math. 17(2):264–275, 2003). 相似文献
4.
On backbone coloring of graphs 总被引:1,自引:0,他引:1
Weifan Wang Yuehua Bu Micka?l Montassier André Raspaud 《Journal of Combinatorial Optimization》2012,23(1):79-93
Let G be a graph and H a subgraph of G. A backbone-k-coloring of (G,H) is a mapping f: V(G)→{1,2,…,k} such that |f(u)−f(v)|≥2 if uv∈E(H) and |f(u)−f(v)|≥1 if uv∈E(G)\E(H). The backbone chromatic number of (G,H) is the smallest integer k such that (G,H) has a backbone-k-coloring. In this paper, we characterize the backbone chromatic number of Halin graphs G=T∪C with respect to given spanning trees T. Also we study the backbone coloring for other special graphs such as complete graphs, wheels, graphs with small maximum
average degree, graphs with maximum degree 3, etc. 相似文献
1