共查询到20条相似文献,搜索用时 500 毫秒
1.
In 2009, Kyaw proved that every -vertex connected -free graph with contains a spanning tree with at most 3 leaves. In this paper, we prove an analogue of Kyaw’s result for connected -free graphs. We show that every -vertex connected -free graph with contains a spanning tree with at most 4 leaves. Moreover, the degree sum condition “” is best possible. 相似文献
2.
3.
4.
5.
A graph is -colorable if it admits a vertex partition into a graph with maximum degree at most and a graph with maximum degree at most . We show that every -free planar graph is -colorable. We also show that deciding whether a -free planar graph is -colorable is NP-complete. 相似文献
6.
7.
For given graphs , , the -color Ramsey number, denoted by , is the smallest integer such that if we arbitrarily color the edges of a complete graph of order with colors, then it always contains a monochromatic copy of colored with , for some . Let be a cycle of length and a star of order . In this paper, firstly we give a general upper bound of . In particular, for the 3-color case, we have and this bound is tight in some sense. Furthermore, we prove that for all and , and if is a prime power, then the equality holds. 相似文献
8.
The tensor product of graphs , and is defined by and Let be the fractional chromatic number of a graph . In this paper, we prove that if one of the three graphs , and is a circular clique, 相似文献
9.
Motivated by Ramsey-type questions, we consider edge-colorings of complete graphs and complete bipartite graphs without rainbow path. Given two graphs and , the -colored Gallai–Ramsey number is defined to be the minimum integer such that and for every , every rainbow -free coloring (using all colors) of the complete graph contains a monochromatic copy of . In this paper, we first provide some exact values and bounds of . Moreover, we define the -colored bipartite Gallai–Ramsey number as the minimum integer such that and for every , every rainbow -free coloring (using all colors) of the complete bipartite graph contains a monochromatic copy of . Furthermore, we describe the structures of complete bipartite graph with no rainbow and , respectively. Finally, we find the exact values of (), (where is a subgraph of ), and by using the structural results. 相似文献
10.
11.
《Discrete Mathematics》2022,345(10):113004
Let G be a graph. We say that G is perfectly divisible if for each induced subgraph H of G, can be partitioned into A and B such that is perfect and . We use and to denote a path and a cycle on t vertices, respectively. For two disjoint graphs and , we use to denote the graph with vertex set and edge set , and use to denote the graph with vertex set and edge set . In this paper, we prove that (i) -free graphs are perfectly divisible, (ii) if G is -free with , (iii) if G is -free, and (iv) if G is -free. 相似文献
12.
13.
《Discrete Mathematics》2019,342(4):1028-1037
For a given pair of two graphs , let be the smallest positive integer such that for any graph of order , either contains as a subgraph or the complement of contains as a subgraph. Baskoro, Broersma and Surahmat (2005) conjectured that for , where is the join of and . In this paper, we prove that this conjecture is true for the case . 相似文献
14.
Building on recent work of Dvořák and Yepremyan, we show that every simple graph of minimum degree contains as an immersion and that every graph with chromatic number at least contains as an immersion. We also show that every graph on vertices with no independent set of size three contains as an immersion. 相似文献
15.
《Discrete Mathematics》2020,343(10):112010
Let be the -partite multigraph in which each part has size , where two vertices in the same part or different parts are joined by exactly edges or edges, respectively. It is proved that there exists a maximal set of edge-disjoint Hamilton cycles in for , the upper bound being best possible. The results proved make use of the method of amalgamations. 相似文献
16.
Let be an array of nonnegative numbers satisfying the recurrence relation with and unless . In this paper, we first prove that the array can be generated by some context-free Grammars, which gives a unified proof of many known results. Furthermore, we present criteria for real rootedness of row-generating functions and asymptotical normality of rows of . Applying the criteria to some arrays related to tree-like tableaux, interior and left peaks, alternating runs, flag descent numbers of group of type , and so on, we get many results in a unified manner. Additionally, we also obtain the continued fraction expansions for generating functions related to above examples. As results, we prove the strong -log-convexity of some generating functions. 相似文献
17.
18.
《Indagationes Mathematicae》2022,33(2):494-516
Current work defines Schmidt representation of a bilinear operator , where and are separable Hilbert spaces. Introducing the concept of singular value and ordered singular value, we prove that if is compact, and its singular values are ordered, then has a Schmidt representation on real Hilbert spaces. We prove that the hypothesis of existence of ordered singular values is fundamental. 相似文献
19.
20.