共查询到20条相似文献,搜索用时 15 毫秒
1.
2.
Cartesian products of complete graphs are known as Hamming graphs. Using embeddings into Cartesian products of quotient graphs we characterize subgraphs, induced subgraphs, and isometric subgraphs of Hamming graphs. For instance, a graph G is an induced subgraph of a Hamming graph if and only if there exists a labeling of E(G) fulfilling the following two conditions: (i) edges of a triangle receive the same label; (ii) for any vertices u and v at distance at least two, there exist two labels which both appear on any induced u, υ‐path. © 2005 Wiley Periodicals, Inc. J Graph Theory 49: 302–312, 2005 相似文献
3.
4.
5.
马刚 《数学的实践与认识》2012,42(9):207-213
研究了一些Mycielski图的点可区别均匀全染色(VDETC),利用构造法给出了路、圈、星和扇的Mycielski图的点可区别均匀全色数,验证了它们满足点可区别均匀全染色猜想(VDETCC). 相似文献
6.
完全二部图广义Mycielski图的邻点可区别全色数与邻强边色数 总被引:6,自引:1,他引:5
得到了完全二部图Km,n的广义Mycielski图Ml(Km,n),当(l≥1,n≥m≥2)时的邻点可区别全色数与邻强边色数. 相似文献
7.
8.
Manu Basavaraju 《Discrete Mathematics》2008,308(24):6650-6653
An acyclic edge coloring of a graph is a proper edge coloring such that there are no bichromatic cycles. The acyclic chromatic index of a graph is the minimum number k such that there is an acyclic edge coloring using k colors and it is denoted by a′(G). From a result of Burnstein it follows that all subcubic graphs are acyclically edge colorable using five colors. This result is tight since there are 3-regular graphs which require five colors. In this paper we prove that any non-regular connected graph of maximum degree 3 is acyclically edge colorable using at most four colors. This result is tight since all edge maximal non-regular connected graphs of maximum degree 3 require four colors. 相似文献
9.
An acyclic edge coloring of a graph G is a proper edge coloring such that no bichromatic cycles are produced. The acyclic chromatic index of G is the smallest integer k such that G has an acyclic edge coloring using k colors. Fiamik (Math. Slovaca 28 (1978), 139–145) and later Alon et al. (J Graph Theory 37 (2001), 157–167) conjectured that for any simple graph G with maximum degree Δ. In this article, we confirm this conjecture for planar graphs of girth at least 4. 相似文献
10.
11.
如果图G的一个正常染色满足染任意两种颜色的顶点集合导出的子图是一些点不交的路的并,则称这个正常染色为图G的线性染色.图G的线性色数用lc(G)表示,是指G的所有线性染色中所用的最少颜色的个数.证明了:若G是一个最大度△(G)≠5,6的平面图,则lc(G)≤2△(G). 相似文献
12.
设G为2-连通平面图,若存在G的面f0,其中f0的边界构成的圈上无弦且V(f0)中的点的度至少为3,使得在G中去掉f0边界上的所有边后得到的图为除V(f0)中的点外度不小于3的树T,则称G为伪-Halin图;若V(f0)中的点全为3度点,则称G为Halin-图.本文研究了这类图的完备色数,并证明了对△(G)≥ 6的伪-Halin图 G有 XC(C)=△(G)+1.其中△(G)和XC(G)分别表示G的最大度和完备色数. 相似文献
13.
14.
A well-established generalization of graph coloring is the concept of list coloring. In this setting, each vertex v of a graph G is assigned a list L(v) of k colors and the goal is to find a proper coloring c of G with c(v)∈L(v). The smallest integer k for which such a coloring c exists for every choice of lists is called the list chromatic number of G and denoted by χl(G).We study list colorings of Cartesian products of graphs. We show that unlike in the case of ordinary colorings, the list chromatic number of the product of two graphs G and H is not bounded by the maximum of χl(G) and χl(H). On the other hand, we prove that χl(G×H)?min{χl(G)+col(H),col(G)+χl(H)}-1 and construct examples of graphs G and H for which our bound is tight. 相似文献
15.
16.
Kishore Yadav Satish Varagani Kishore Kothapalli V.Ch. Venkaiah 《Discrete Mathematics》2011,311(5):748
An acyclic vertex coloring of a graph is a proper vertex coloring such that there are no bichromatic cycles. The acyclic chromatic number of G, denoted a(G), is the minimum number of colors required for acyclic vertex coloring of graph G. For a family F of graphs, the acyclic chromatic number of F, denoted by a(F), is defined as the maximum a(G) over all the graphs G∈F. In this paper we show that a(F)=8 where F is the family of graphs of maximum degree 5 and give a linear time algorithm to achieve this bound. 相似文献
17.
Given a graph G=(V, E), let ${\mathcal{P}}$ be a partition of V. We say that ${\mathcal{P}}$ is dominating if, for each part P of ${\mathcal{P}}$, the set V\P is a dominating set in G (equivalently, if every vertex has a neighbor of a different part from its own). We say that ${\mathcal{P}}$ is acyclic if for any parts P, P′ of ${\mathcal{P}}$, the bipartite subgraph G[P, P′] consisting of the edges between P and P′ in ${\mathcal{P}}$ contains no cycles. The acyclic dominating number ad(G) of G is the least number of parts in any partition of V that is both acyclic and dominating; and we shall denote by ad(d) the maximum over all graphs G of maximum degree at most d of ad(G). In this article, we prove that ad(3)=2, which establishes a conjecture of P. Boiron, É. Sopena, and L. Vignal, DIMACS/DIMATIA Conference “Contemporary Trends in Discrete Mathematics”, 1997, pp. 1–10. For general d, we prove the upper bound ad(d)=O(dlnd) and a lower bound of ad(d)=Ω(d). © 2009 Wiley Periodicals, Inc. J Graph Theory 64: 292–311, 2010 相似文献
18.
Every planar graph is known to be acyclically 7-choosable and is conjectured to be acyclically 5-choosable (Borodin et al. 2002) [7]. This conjecture if proved would imply both Borodin’s acyclic 5-color theorem (1979) and Thomassen’s 5-choosability theorem (1994). However, as yet it has been verified only for several restricted classes of graphs.Some sufficient conditions are also obtained for a planar graph to be acyclically 4-choosable and 3-choosable. In particular, acyclic 4-choosability was proved for the following planar graphs: without 3-cycles and 4-cycles (Montassier, 2006 [23]), without 4-cycles, 5-cycles and 6-cycles (Montassier et al. 2006 [24]), and either without 4-cycles, 6-cycles and 7-cycles, or without 4-cycles, 6-cycles and 8-cycles (Chen et al. 2009 [14]).In this paper it is proved that each planar graph with neither 4-cycles nor 6-cycles adjacent to a triangle is acyclically 4-choosable, which covers these four results. 相似文献
19.
A.V. Kostochka 《Journal of Graph Theory》2014,75(4):377-386
Let denote the graph obtained from the complete graph by deleting the edges of some ‐subgraph. The author proved earlier that for each fixed s and , every graph with chromatic number has a minor. This confirmed a partial case of the corresponding conjecture by Woodall and Seymour. In this paper, we show that the statement holds already for much smaller t, namely, for . 相似文献
20.
A proper vertex coloring of a graph G=(V,E) is acyclic if G contains no bicolored cycle. Given a list assignment L={L(v)∣v∈V} of G, we say G is acyclically L-list colorable if there exists a proper acyclic coloring π of G such that π(v)∈L(v) for all v∈V. If G is acyclically L-list colorable for any list assignment with |L(v)|≥k for all v∈V, then G is acyclically k-choosable. In this paper we prove that planar graphs without 4, 7, and 8-cycles are acyclically 4-choosable. 相似文献