共查询到18条相似文献,搜索用时 594 毫秒
1.
2.
3.
4.
5.
6.
一个图G的全色数χT(G)是使得V(G)∪E(G)中相邻或相关联元素均染不同颜色的最少颜色数.文中证明了,若图G只有唯一的一个4度最大度点,则χT(G)=Δ(G)+1. 相似文献
7.
关于图的均匀全色数分类 总被引:1,自引:0,他引:1
对一个正常的全染色满足各种颜色所染元素数(点或边)相差不超过1时,称为均匀全染色,其所用最少染色数称为均匀全色数.将图按均匀全色数分类,证明了简单图在若干情况下的均匀全色数定理,得到了一些联图的均匀全色数. 相似文献
8.
9.
对一个正常的全染色满足各种颜色所染元素数(点或边)相差不超过1时,称为均匀全染色,其所用最少染色数称为均匀全色数.本文证明了图在若干情况下的均匀全色数定理,得到C_m∨S_nC_m∨ F_n和C∨W_n的均匀全色数. 相似文献
10.
11.
Given a graph G, for each υ ∈V(G) let L(υ) be a list assignment to G. The well‐known choice number c(G) is the least integer j such that if |L(υ)| ≥j for all υ ∈V(G), then G has a proper vertex colouring ? with ?(υ) ∈ L (υ) (?υ ∈V(G)). The Hall number h(G) is like the choice number, except that an extra non‐triviality condition, called Hall's condition, has to be satisfied by the list assignment. The edge‐analogue of the Hall number is called the Hall index, h′(G), and the total analogue is called the total Hall number, h″(G), of G. If the stock of colours from which L(υ) is selected is restricted to a set of size k, then the analogous numbers are called k‐restricted, or restricted, Hall parameters, and are denoted by hk(G), h′k(G) and h″k(G). Our main object in this article is to determine, or closely bound, h′(K), h″(Kn), h′(Km,n) and h′k(Km,n). We also answer some hitherto unresolved questions about Hall parameters. We show in particular that there are examples of graphs G with h′(G)?h′(G ? e)>1. We show that there are examples of graphs G and induced subgraphs H with hk(G)<hk(H) [this phenomenon cannot occur with unrestricted Hall numbers]. We also give an example of a graph G and an integer k such that hk(G)<χ(G)<h(G). © 2002 Wiley Periodicals, Inc. J Graph Theory 41: 208–237, 2002 相似文献
12.
The total chromatic number χT (G) of a graph G is the minimum number of colors needed to color the edges and the vertices of G so that incident or adjacent elements have distinct colors. We show that if G is a regular graph and d(G) 32 |V (G)| + 263 , where d(G) denotes the degree of a vertex in G, then χT (G) d(G) + 2. 相似文献
13.
Tomáš Kaiser Andrew King Daniel Král? 《Journal of Combinatorial Theory, Series B》2011,101(6):383-402
Reed conjectured that for every ?>0 and Δ there exists g such that the fractional total chromatic number of a graph with maximum degree Δ and girth at least g is at most Δ+1+?. We prove the conjecture for Δ=3 and for even Δ?4 in the following stronger form: For each of these values of Δ, there exists g such that the fractional total chromatic number of any graph with maximum degree Δ and girth at least g is equal to Δ+1. 相似文献
14.
为了找到联图P_m∨C_n及C_m∨C_n的点可区别全染色利用其组合度用构造法得到了P_m∨C_n及C_m∨C_n的点可区别全染色方法并得到了其点可区别全色数(m≠n). 相似文献
15.
Jonathan Hulgan 《Discrete Mathematics》2009,309(8):2548-2550
Let G=(V,E) be a graph and f:(V∪E)→[k] be a proper total k-coloring of G. We say that f is an adjacent vertex- distinguishing total coloring if for any two adjacent vertices, the set of colors appearing on the vertex and incident edges are different. We call the smallest k for which such a coloring of G exists the adjacent vertex-distinguishing total chromatic number, and denote it by χat(G). Here we provide short proofs for an upper bound on the adjacent vertex-distinguishing total chromatic number of graphs of maximum degree three, and the exact values of χat(G) when G is a complete graph or a cycle. 相似文献
16.
A multicircuit is a multigraph whose underlying simple graph is a circuit (a connected 2‐regular graph). In this paper, the method of Alon and Tarsi is used to prove that all multicircuits of even order, and some regular and near‐regular multicircuits of odd order have total choosability (i.e., list total chromatic number) equal to their ordinary total chromatic number. This completes the proof that every multicircuit has total choosability equal to its total chromatic number. In the process, the total chromatic numbers of all multicircuits are determined. © 2002 Wiley Periodicals, Inc. J Graph Theory 40: 44–67, 2002 相似文献
17.
设 $G$ 是一个简单图. 设$f$是从$V(G) \cup E(G)$到 $\{1, 2,\ldots, k\}$的一个映射.对任意的 $v\in V(G)$, 设$C_f(v)=\{f(v)\}\cup \{f (vw)|w\in V(G),vw\in E(G)\}$ . 如果 $f$ 是一个 $k$-正常全染色, 且对 $u, v\in V(G),uv\in E(G)$, 有 $C_f(u)\neq C_f(v)$, 那么称 $f$ 为$k$-邻点可区别全染色 (简记为$k$-$AVDTC$). 设 相似文献
18.
马刚 《数学的实践与认识》2012,42(9):207-213
研究了一些Mycielski图的点可区别均匀全染色(VDETC),利用构造法给出了路、圈、星和扇的Mycielski图的点可区别均匀全色数,验证了它们满足点可区别均匀全染色猜想(VDETCC). 相似文献