共查询到20条相似文献,搜索用时 46 毫秒
1.
《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. 相似文献
2.
Christian Bosse 《Discrete Mathematics》2019,342(12):111595
The Hadwiger number of a graph , denoted , is the largest integer such that contains as a minor. A famous conjecture due to Hadwiger in 1943 states that for every graph , , where denotes the chromatic number of . Let denote the independence number of . A graph is -free if it does not contain the graph as an induced subgraph. In 2003, Plummer, Stiebitz and Toft proved that for all -free graphs with , where is any graph on four vertices with , , or is a particular graph on seven vertices. In 2010, Kriesell subsequently generalized the statement to include all forbidden subgraphs on five vertices with . In this note, we prove that for all -free graphs with , where denotes the wheel on six vertices. 相似文献
3.
《Discrete Mathematics》2022,345(8):112903
Graphs considered in this paper are finite, undirected and loopless, but we allow multiple edges. The point partition number is the least integer k for which G admits a coloring with k colors such that each color class induces a -degenerate subgraph of G. So is the chromatic number and is the point arboricity. The point partition number with was introduced by Lick and White. A graph G is called -critical if every proper subgraph H of G satisfies . In this paper we prove that if G is a -critical graph whose order satisfies , then G can be obtained from two non-empty disjoint subgraphs and by adding t edges between any pair of vertices with and . Based on this result we establish the minimum number of edges possible in a -critical graph G of order n and with , provided that and t is even. For the corresponding two results were obtained in 1963 by Tibor Gallai. 相似文献
4.
《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 . 相似文献
5.
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. 相似文献
6.
7.
《Discrete Mathematics》2019,342(3):898-903
8.
9.
10.
《Discrete Mathematics》2022,345(5):112801
Let G and H be simple graphs. The Ramsey number is the minimum integer N such that any red-blue-coloring of edges of contains either a red copy of G or a blue copy of H. Let denote m vertex-disjoint copies of . A lower bound is that . Burr, Erd?s and Spencer proved that this bound is indeed the Ramsey number for , and . In this paper, we show that this bound is the Ramsey number for and . We also show that this bound is the Ramsey number for and . 相似文献
11.
12.
13.
14.
《Discrete Mathematics》2022,345(3):112717
A transversal set of a graph G is a set of vertices incident to all edges of G. The transversal number of G, denoted by , is the minimum cardinality of a transversal set of G. A simple graph G with no isolated vertex is called τ-critical if for every edge . For any τ-critical graph G with , it has been shown that by Erd?s and Gallai and that by Erd?s, Hajnal and Moon. Most recently, it was extended by Gyárfás and Lehel to . In this paper, we prove stronger results via spectrum. Let G be a τ-critical graph with and , and let denote the largest eigenvalue of the adjacency matrix of G. We show that with equality if and only if G is , , or , where ; and in particular, with equality if and only if G is . We then apply it to show that for any nonnegative integer r, we have and characterize all extremal graphs. This implies a pure combinatorial result that , which is stronger than Erd?s-Hajnal-Moon Theorem and Gyárfás-Lehel Theorem. We also have some other generalizations. 相似文献
15.
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. 相似文献
16.
17.
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. 相似文献
18.
19.
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. 相似文献
20.
《Discrete Mathematics》2019,342(10):2834-2842