共查询到20条相似文献,搜索用时 78 毫秒
1.
《数学的实践与认识》2015,(23)
对图G的一个正常边染色,如果图G的任何一个圈至少染三种颜色,则称这个染色为无圈边染色.若L为图G的一个边列表,对图G的一个无圈边染色φ,如果对任意e∈E(G)都有ф(e)∈L(e),则称ф为无圈L-边染色.用a′_(list)(G)表示图G的无圈列表边色数.证明若图G是一个平面图,且它的最大度△≥8,围长g(G)≥6,则a′_(list)(G)=△. 相似文献
2.
3.
4.
设G=(V,E)是一个图,一个函数f:E→{-1,+1},如果对于G中至少k条边e有sum from e'∈N[e]f(e')≥1成立,则称f为图G的一个k符号边控制函数.一个图的k符号边控制数定义为γ_(ks)/(G)=min{∑_(e∈E(G))f(e)|f为图G的一个k符号边控制函数}.主要给出了一个图G的k符号边控制数γ_(ks)/(G)=min{∑_(e∈E(G))f(e)|f为图G的一个k符号边控制函数}.主要给出了一个图G的k符号边控制数γ_(ks)/(G)的若干新下限,并确定了路和圈的k符号边控制数. 相似文献
5.
记[k]={1,2,…,k),称为颜色集.设φ:E(G)→[k]为图G的边集合到[k]的映射,令f(v)表示与顶点v关联的边的颜色的加和.如果对任意一条边uv∈E(G),都有φ(u)≠φ(v),f(u)≠f(v),则称φ为图G的邻和可区别[k]-边染色,k的最小值称为图G的邻和可区别边色数,记为ndi_Σ(G).若对任意一条边uv∈E(G),都有f(u)≠f(v),则称φ为图G的k-边权点染色,称图G是k-边权可染的.运用组合零点定理证明了对于最大度不等于4的Halin图有:ndi_∑(G)≤Δ(G)+2,并证明了任一Halin图是4-边权可染的. 相似文献
6.
7.
8.
9.
对于简单图G=〈V,E〉,如果存在一个映射f:V(G)→{0,1,2,…,2|E|-1}满足:1)对任意的u,v∈V,若u≠v,则f(u)≠f(v);2)max{f(v)|v∈V}=2|E|-1;3)对任意的e_1,e_2∈E,若e_1≠e_2,则g(e_1)≠g(e_2),此处g(e)=|f(u)+f(v)|,e=uv;4)|g(e)|e∈E}={1,3,5,…,2|E|-1},则称G为奇优美图,f称为G的奇优美标号.设G=〈V,E〉是一个无向简单图.如果存在一个映射f:V(G)→{0,1,2,…,2|E|-1},满足:1)f是单射;2)■uv∈E(G),令f(uv)=f(u)+f(v),有{f(uv)|uv∈E(G)}={1,3,5,…,2|E|-1},则称G是奇强协调图,f称为G的.奇强协调标号或奇强协调值.给出了链图、升降梯等几类有趣图的奇优美标号和奇强协调标号. 相似文献
10.
Pm×Kn的邻点可区别全色数 总被引:6,自引:0,他引:6
设G是简单图.设f是一个从V(G)∪E(G)到{1,2,…,k}的映射.对每个v∈V(G),令C_f(v)={f(v)}∪{f(vw)|w∈V(G),vw∈E(G)}.如果f是k-正常全染色,且对任意u,v∈V(G),uv∈E(G),有C_f(u)≠C_f(v),那么称f为图G的邻点可区别全染色(简称为k-AVDTC).数x_(at)(G)=min{k|G有k-AVDTC}称为图G的邻点可区别全色数.本文给出路P_m和完全图K_n的Cartesion积的邻点可区别全色数. 相似文献
11.
Michael J. Pelsmajer 《Journal of Graph Theory》2009,61(2):127-139
Given lists of available colors assigned to the vertices of a graph G, a list coloring is a proper coloring of G such that the color on each vertex is chosen from its list. If the lists all have size k, then a list coloring is equitable if each color appears on at most ?|V(G)|/k? vertices. A graph is equitably k ‐choosable if such a coloring exists whenever the lists all have size k. Kostochka, Pelsmajer, and West introduced this notion and conjectured that G is equitably k‐choosable for k>Δ(G). We prove this for graphs of treewidth w≤5 if also k≥3w?1. We also show that if G has treewidth w≥5, then G is equitably k‐choosable for k≥max{Δ(G)+w?4, 3w?1}. As a corollary, if G is chordal, then G is equitably k‐choosable for k≥3Δ(G)?4 when Δ(G)>2. © 2009 Wiley Periodicals, Inc. J Graph Theory 相似文献
12.
Abstract A k-edge-coloring f of a connected graph G is a (A1, A2, , A)-defected k-edge-coloring if there is a smallest integer/ with 1 _ /3 _〈 k - i such that the multiplicity of each color j E {1,2,... ,/3} appearing at a vertex is equal to Aj _〉 2, and each color of {/3 -}- 1,/3 - 2, - , k} appears at some vertices at most one time. The (A1, A2,, A/)-defected chromatic index of G, denoted as X (A1, A2,, A/; G), is the smallest number such that every (A1,A2,-.., A/)-defected t-edge-coloring of G holds t _〉 X(A1, A2 A;; G). We obtain A(G) X(A1, )2, , A/; G) + -- (Ai - 1) _〈 /k(G) 1, and introduce two new chromatic indices of G i=1 as: the vertex pan-biuniform chromatic index X pb (G), and the neighbour vertex pan-biuniform chromatic index Xnpb(G), and furthermore find the structure of a tree T having X pb (T) =1. 相似文献
13.
Michael Molloy 《Journal of Graph Theory》2017,84(1):53-56
We prove that the adaptable chromatic number of a graph is at least asymptotic to the square root of the chromatic number. This is best possible. 相似文献
14.
15.
A graph G is k‐choosable if its vertices can be colored from any lists L(ν) of colors with |L(ν)| ≥ k for all ν ∈ V(G). A graph G is said to be (k,?)‐choosable if its vertices can be colored from any lists L(ν) with |L(ν)| ≥k, for all ν∈ V(G), and with . For each 3 ≤ k ≤ ?, we construct a graph G that is (k,?)‐choosable but not (k,? + 1)‐choosable. On the other hand, it is proven that each (k,2k ? 1)‐choosable graph G is O(k · ln k · 24k)‐choosable. © 2005 Wiley Periodicals, Inc. J Graph Theory 相似文献
16.
The adaptable choosability number of a multigraph G, denoted cha(G), is the smallest integer k such that every edge labeling of G and assignment of lists of size k to the vertices of G permits a list coloring of G in which no edge e=uv has both u and v colored with the label of e. We show that cha grows with ch, i.e. there is a function f tending to infinity such that cha(G)≥f(ch(G)). 相似文献
17.
Maria Axenovich Heiko Harborth Arnfried Kemnitz Meinhard Möller Ingo Schiermeyer 《Graphs and Combinatorics》2007,23(2):123-133
Let Qn be a hypercube of dimension n, that is, a graph whose vertices are binary n-tuples and two vertices are adjacent iff the corresponding n-tuples differ in exactly one position. An edge coloring of a graph H is called rainbow if no two edges of H have the same color. Let f(G,H) be the largest number of colors such that there exists an edge coloring of G with f(G,H) colors such that no subgraph isomorphic to H is rainbow. In this paper we start the investigation of this anti-Ramsey problem by providing bounds on f(Qn,Qk) which are asymptotically tight for k = 2 and by giving some exact results. 相似文献
18.
The star chromatic index of a graph G is the minimum number of colors needed to properly color the edges of the graph so that no path or cycle of length four is bi‐colored. We obtain a near‐linear upper bound in terms of the maximum degree . Our best lower bound on in terms of Δ is valid for complete graphs. We also consider the special case of cubic graphs, for which we show that the star chromatic index lies between 4 and 7 and characterize the graphs attaining the lower bound. The proofs involve a variety of notions from other branches of mathematics and may therefore be of certain independent interest. 相似文献
19.
《Discrete Mathematics》2019,342(11):3025-3033
20.