共查询到17条相似文献,搜索用时 296 毫秒
1.
图的星色数的概念是Vince在1988年提出的,它是图的色数的一个推广.本文构造了一类星色数是4的平面图. 相似文献
2.
图的星色数是通常色数概念的推广.本文求出了几类由轮图导出的平面图的星色数.前两类是由3-或5-轮图经细分等构造出的,其星色数分别为2+2/(2n+1),2+3/(3n+1)和2+3/(3n-1).第三类平面图是由n-轮图经过Hajos构造得到的,其星色数为3+1/n.本类图的星色数结果推广了已有结论. 相似文献
3.
5.
1988年,Vince定义了图的色数的一个推广——图的星色数,本文研究了有围长限制或有最大度限制的临界图的星色数,得到了三个新结果。 相似文献
6.
这篇注记证明判断一个图是否有3-正则子图的问题,即使对于节点次不超过4的平面图,仍然是NP-完全的。而且,此结果是最好的可能。 相似文献
7.
9.
给出了平面图为第一类图的边数的一些上界,并给出了平面图为第一类图的一些充分条件. 相似文献
10.
三正则平面图的对偶图的哈密顿性的注记 总被引:1,自引:0,他引:1
陈婵 《高校应用数学学报(A辑)》2001,16(2):248-250
本文给出了三正则平面图的对偶图为哈密顿图的一个充分条件。 相似文献
11.
12.
De Ming Li 《数学学报(英文版)》2002,18(1):173-180
The notion of the star chromatic number of a graph is a generalization of the chromatic number. In this paper, we calculate
the star chromatic numbers of three infinite families of planar graphs. The first two families are derived from a 3-or 5-wheel
by subdivisions, their star chromatic numbers being 2+2/(2n + 1), 2+3/(3n + 1), and 2+3(3n−1), respectively. The third family of planar graphs are derived from n odd wheels by Hajos construction with star chromatic numbers 3 + 1/n, which is a generalization of one result of Gao et al.
Received September 21, 1998, Accepted April 9, 2001. 相似文献
13.
三类笛卡尔积图的关联色数 总被引:2,自引:0,他引:2
图的关联色数的概念是 Brualdi和 Massey于 1 993年引入的 ,它同图的强色指数有密切的关系 .Guiduli[2 ] 说明关联色数是有向星萌度的一个特殊情况 ,迄今仅确定了某些特殊图类的关联色数 .本文给出了完全图与完全图、圈与完全图、圈与圈的笛卡尔积图的关联色数。 相似文献
14.
There are numerous means for measuring the closeness to planarity of a graph such as crossing number, splitting number, and
a variety of thickness parameters. We focus on the classical concept of the thickness of a graph, and we add to earlier work
in [4]. In particular, we offer new 9-critical thickness-two graphs on 17, 25, and 33 vertices, all of which provide counterexamples
to a conjecture on independence ratio of Albertson; we investigate three classes of graphs, namely singly and doubly outerplanar
graphs, and cloned planar graphs. We give a sharp upper bound for the largest chromatic number of the cloned planar graphs,
and we give upper and lower bounds for the largest chromatic number of the former two classes. 相似文献
15.
A main result of combinatorial optimization is that clique and chromatic number of a perfect graph are computable in polynomial time (Grötschel et al. in Combinatorica 1(2):169–197, 1981). Perfect graphs have the key property that clique and chromatic number coincide for all induced subgraphs; we address the question whether the algorithmic results for perfect graphs can be extended to graph classes where the chromatic number of all members is bounded by the clique number plus one. We consider a well-studied superclass of perfect graphs satisfying this property, the circular-perfect graphs, and show that for such graphs both clique and chromatic number are computable in polynomial time as well. In addition, we discuss the polynomial time computability of further graph parameters for certain subclasses of circular-perfect graphs. All the results strongly rely upon Lovász’s Theta function. 相似文献
16.
Star chromatic numbers of graphs 总被引:10,自引:0,他引:10
We investigate the relation between the star-chromatic number (G) and the chromatic number (G) of a graphG. First we give a sufficient condition for graphs under which their starchromatic numbers are equal to their ordinary chromatic numbers. As a corollary we show that for any two positive integersk, g, there exists ak-chromatic graph of girth at leastg whose star-chromatic number is alsok. The special case of this corollary withg=4 answers a question of Abbott and Zhou. We also present an infinite family of triangle-free planar graphs whose star-chromatic number equals their chromatic number. We then study the star-chromatic number of An infinite family of graphs is constructed to show that for each >0 and eachm2 there is anm-connected (m+1)-critical graph with star chromatic number at mostm+. This answers another question asked by Abbott and Zhou. 相似文献
17.
《Discrete Mathematics》2023,346(1):113162
The graph coloring game is a two-player game in which the two players properly color an uncolored vertex of G alternately. The first player wins the game if all vertices of G are colored, and the second wins otherwise. The game chromatic number of a graph G is the minimum integer k such that the first player has a winning strategy for the graph coloring game on G with k colors. There is a lot of literature on the game chromatic number of graph products, e.g., the Cartesian product and the lexicographic product. In this paper, we investigate the game chromatic number of the strong product of graphs, which is one of major graph products. In particular, we completely determine the game chromatic number of the strong product of a double star and a complete graph. Moreover, we estimate the game chromatic number of some King's graphs, which are the strong products of two paths. 相似文献