剖分点一边冠图的电阻距离和Kirchhoff指标（英文）

图G的剖分图S(G)是在图G的每条边上加一个顶点.这些新添加的点的集合称为I(G).在三个图G_1,G_2和G_3的基础上引进了一种新的图运算,称为剖分点一边冠图,记作G_1~So(G_2~V∪G_3~E),它由S(G_1),|V(G_1|个G_2的拷贝和|I(G_1|个G_3的拷贝组成,将V(G_1)中的第i个顶点和第i个G_2的拷贝中的每个顶点连接,同时将I(G1)中的第i个顶点和第i个G_3的拷贝中的每个顶点连接.本文给出了剖分点一边冠图的电阻距离和Kirchhoff指标.     

不含5-圈和相邻6-圈的平面图的全染色

图的正常k-全染色是用k种颜色给图的顶点和边同时进行染色,使得相邻或者相关联的元素(顶点或边)染不同的染色.使得图G存在正常k-全染色的最小正整数k,称为图G的全色数,用χ″(G)表示.证明了若图G是最大度△≥6且不含5-圈和相邻6-圈的平面图,则χ″(G)=△+1.     

完全多部图的树划分数的直观证明

r-边染色图G的树划分数tr(G)定义为最小的正整数k,使得只要用r种颜色对图G进行边染色,则存在至多k个顶点不交的单色树覆盖图G的所有顶点.K aneko等确定了t2(K(n1,n2,…,nk))的精确表达式.本文给出了该表达式的一个直观证明.     

外平面图的有界染色

图G的k-有界染色是图G的一个最多有k个顶点染同一种颜色的顶点染色．图 G的k-有界染色数Xk(G)是指对G进行k-有界染色用的最少颜色数．本文给出了n个顶点的外平面图能用[n/k]种颜色k-有界染色的一些充分条件．     

mC4的顶点被多重色集合可区别的一般边染色北大核心CSCD

简单图G的一个一般边染色是指若干种颜色关于图G的所有边的一个分配,不要求相邻的边被分配不同的颜色.设f是G的使用了k种颜色的一般边染色,若对(?)u,v∈V(G),u≠v,都有与u关联的边的颜色构成的多重集合异于与v关联的边的颜色构成的多重集合,那么称f是使用了k种颜色的顶点被多重色集合可区别的一般边染色.对G进行顶点被多重色集合可区别的一般边染色所需的最少颜色数记为c(G),并且称c(G)为图G的顶点被多重色集合可区别的一般边色数.本文确定了m个C_4的点不交的并mC_4的顶点被多重色集合可区别的一般边色数.     

不含4-圈和5-圈的平面图的非正常2-染色的一个新结果

设d_1,d_2,···,d_k是k个非负整数,若图G=(V,E)的顶点集V能被剖分成k个子集V_1,V_2,···,V_k,使得对任意的i=1,···,k,V_i的点导出子图G[Vi]的最大度至多为di,则称图G是(d_1,d_2,···,d_k)-可染的,本文证明了既不含4-圈又不含5-圈的平面图是(9,9)-可染的.     

路的字典积的邻和可区别边染色

图G的正常[k]-边染色σ是指颜色集合为[k]={1,2,...,k}的G的一个正常边染色.用w_σ(χ)表示顶点χ关联边的颜色之和,即■,并称w_σ(x)为x关于σ的权.图G的k-邻和可区别边染色是指相邻顶点具有不同权的正常[k]-边染色,最小的k值称为G的邻和可区别边色数,记为x′_Σ(G).现得到了路P_n与简单连通图H的字典积P_n[H]的邻和可区别边色数的精确值,其中H分别为正则第一类图、路、完全图的补图.     

不含4-,6-圈和相交三角形的平面图的无圈边色数

图G的一个边染色φ:E(G)→{1,2,…,k},若满足任意相邻边都染不同的颜色,且图G不存在双色圈,则称φ为图G的一个无圈k-边染色.图G的无圈边色数χ’_α(G)为使得图G有一个无圈k-边染色的最小正整数k.本文主要证明了对于无4-,6-圈且3-圈与3-圈不相交的平面图G,若Δ(G)≥9,则χ’_α(G)≤Δ(G)+1.     

包装{(p,p-1),(p,p)}图对和 Slater 问题

设 G 是一个简单无向图.V(G),E(G)分别表示 G 的顶点集和边集.(?)表示 G 的补图.我们以 S_(?) 表示 n 1阶星图 k_(1,n-1).称 G 是(p,p—k)图,如果|E(G)|=|V(G)|—k.称|V(G)|为图 G 的阶.设 G_1,G_2是同阶图,(?)_1是 V(G_1)到 V(G_2)的一个双射,(?)_2是 V(G_2)上的一个置换,我们用(?)_2(?)_1表示 V(G_1)到 V(G_2)的双射,其作用为     

线图上的团染色问题

设G=(V,E)为简单图, G的每个至少有两个顶点的极大完全子图称为G的一个团. 图的团染色定义为给图的点进行染色使得图中没有单一颜色的团, 也就是说每一个团具有至少2种颜色.图的一个k-团染色 是指用k 种颜色给图的点着色使得图G 的每一个团至少有2种颜色.图G的团染色数\chi_{C}(G)是指最小的数k使得图G 存在k-团染色. 首先指出了完全图的线图的团染色数与推广的Ramsey 数之间的一个联系, 其次对于最大度不超过7的线图给出了一个最优团染色的多项式时间算法.     

b-Chromatic Number of Cartesian Product of Some Families of Graphs

A b-coloring of a graph G with k colors is a proper coloring of G using k colors in which each color class contains a color dominating vertex, that is, a vertex which has a neighbor in each of the other color classes. The largest positive integer k for which G has a b-coloring using k colors is the b-chromatic number b(G) of G. It is known that for any two graphs G and H, ${b(G \square H) \geq {\rm {max}} \{b(G), b(H)\}}$ , where ${\square}$ stands for the Cartesian product. In this paper, we determine some families of graphs G and H for which strict inequality holds. More precisely, we show that for these graphs G and H, ${b(G \square H) \geq b(G) + b(H) - 1}$ . This generalizes one of the results due to Kouider and Mahéo.     

On minimally b-imperfect graphs

A b-coloring is a coloring of the vertices of a graph such that each color class contains a vertex that has a neighbour in all other color classes. The b-chromatic number of a graph G is the largest integer k such that G admits a b-coloring with k colors. A graph is b-perfect if the b-chromatic number is equal to the chromatic number for every induced subgraph H of G. A graph is minimally b-imperfect if it is not b-perfect and every proper induced subgraph is b-perfect. We give a list of minimally b-imperfect graphs, conjecture that a graph is b-perfect if and only if it does not contain a graph from this list as an induced subgraph, and prove this conjecture for diamond-free graphs, and graphs with chromatic number at most three.     

On the b-continuity property of graphs

This paper deals with b-colorings of a graph G, that is, proper colorings in which for each color c, there exists at least one vertex colored by c such that its neighbors are colored by each other color. The b-chromatic numberb(G) of a graph G is the maximum number of colors for which G has a b-coloring. It is easy to see that every graph G has a b-coloring using χ(G) colors.We say that G is b-continuous iff for each k, χ(G)?k?b(G), there exists a b-coloring with k colors. It is well known that not all graphs are b-continuous. We call b-spectrumS_b(G) of G to be the set of integers k for which there is a b-coloring of G by k colors. We show that for any finite integer set I, there exists a graph whose b-spectrum is I and we investigate the complexity of the problem of deciding whether a graph G is b-continuous, even if b-colorings using χ(G) and b(G) colors are given.     

On the b-Coloring of Cographs and <Emphasis Type="Italic">P</Emphasis><Subscript>4</Subscript>-Sparse Graphs

A b-coloring of a graph is a coloring such that every color class admits a vertex adjacent to at least one vertex receiving each of the colors not assigned to it. The b-chromatic number of a graph G, denoted by χ _b (G), is the maximum number t such that G admits a b-coloring with t colors. A graph G is b-continuous if it admits a b-coloring with t colors, for every . We define a graph G to be b-monotonic if χ _b (H ₁) ≥ χ _b (H ₂) for every induced subgraph H ₁ of G, and every induced subgraph H ₂ of H ₁. In this work, we prove that P ₄-sparse graphs (and, in particular, cographs) are b-continuous and b-monotonic. Besides, we describe a dynamic programming algorithm to compute the b-chromatic number in polynomial time within these graph classes. Flavia Bonomo: Partially supported by ANPCyT PICT-2007-00533 and PICT-2007-00518, and UBACyT Grants X069 and X606 (Argentina). Guillermo Durán: Partially supported by FONDECyT Grant 1080286 and Millennium Science Institute “Complex Engineering Systems” (Chile), and ANPCyT PICT-2007-00518 and UBACyT Grant X069 (Argentina). Javier Marenco: Partially supported by ANPCyT PICT-2007-00518 and UBACyT Grant X069 (Argentina).     

On b-perfect Chordal Graphs

The b-chromatic number of a graph G is the largest integer k such that G has a coloring of the vertices in k color classes such that every color class contains a vertex that has a neighbour in all other color classes. We characterize the class of chordal graphs for which the b-chromatic number is equal to the chromatic number for every induced subgraph. This research was supported by Algerian-French program CMEP/Tassili 05 MDU 639.     

The Rainbow Vertex-disconnection in Graphs

Let G be a nontrivial connected and vertex-colored graph. A subset X of the vertex set of G is called rainbow if any two vertices in X have distinct colors. The graph G is called rainbow vertex-disconnected if for any two vertices x and y of G, there exists a vertex subset S of G such that when x and y are nonadjacent, S is rainbow and x and y belong to different components of G-S; whereas when x and y are adjacent, S + x or S + y is rainbow and x and y belong to different components of(G-xy)-S. For a connected graph G, the rainbow vertex-disconnection number of G, denoted by rvd(G), is the minimum number of colors that are needed to make G rainbow vertexdisconnected. In this paper, we characterize all graphs of order n with rainbow vertex-disconnection number k for k ∈ {1, 2, n}, and determine the rainbow vertex-disconnection numbers of some special graphs. Moreover, we study the extremal problems on the number of edges of a connected graph G with order n and rvd(G) = k for given integers k and n with 1 ≤ k ≤ n.     

The b-Chromatic Number of Cubic Graphs

The b-chromatic number of a graph G is the largest integer k such that G admits a proper k-coloring in which every color class contains at least one vertex adjacent to some vertex in all the other color classes. It is proved that with four exceptions, the b-chromatic number of cubic graphs is 4. The exceptions are the Petersen graph, K _3,3, the prism over K ₃, and one more sporadic example on 10 vertices.     

某些中间图的邻点可区别E-全色数

设G（V,E）是简单连通图,T（G）为图G的所有顶点和边构成的集合,并设C是k-色集（k是正整数）,若T（G）到C的映射f满足：对任意uv∈E（G）,有f（u）≠f（v）,f（u）≠f（uv）,f（v）≠f（uv）,并且C（u）≠C（v）,其中C（u）={f（u）}∪{f（uv）｜uv∈E（G）}.那么称f为图G的邻点可区别E-全染色（简记为k-AVDETC）,并称χ_（at）~e（G）=min{k｜图G有k-邻点可区别E-全染色}为G的邻点可区别E-全色数.图G的中间图M（G）就是在G的每一个边上插入一个新的顶点,再把G上相邻边上的新的顶点相联得到的.探讨了路、圈、扇、星及轮的中间图的邻点可区别E-全染色,并给出了这些中间图的邻点可区别E-全色数.     

Vertex-distinguishing IE-total Colorings of Complete Bipartite Graphs K8,n

Let G be a simple graph. An IE-total coloring f of G is a coloring of the vertices and edges of G so that no two adjacent vertices receive the same color. For each vertex x of G, let C(x) be the set of colors of vertex x and edges incident to x under f. For an IE-total coloring f of G using k colors, if C(u) 6= C(v) for any two different vertices u and v of G, then f is called a k-vertex-distinguishing IE-total-coloring of G or a k-VDIET coloring of G for short. The minimum number of colors required for a VDIET coloring of G is denoted by χievt(G) and is called vertex-distinguishing IE-total chromatic number or the VDIET chromatic number of G for short. The VDIET colorings of complete bipartite graphs K8,n are discussed in this paper. Particularly, the VDIET chromatic number of K8,n are obtained.