共查询到20条相似文献,搜索用时 156 毫秒
1.
《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. 相似文献
2.
《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. 相似文献
3.
4.
Julia Semikina 《Journal of Pure and Applied Algebra》2019,223(10):4509-4523
I. Hambleton, L. Taylor and B. Williams conjectured a general formula in the spirit of H. Lenstra for the decomposition of for any finite group G and noetherian ring R. The conjectured decomposition was shown to hold for some large classes of finite groups. D. Webb and D. Yao discovered that the conjecture failed for the symmetric group , but remarked that it still might be reasonable to expect the HTW-decomposition for solvable groups. In this paper we show that the solvable group is also a counterexample to the conjectured HTW-decomposition. Nevertheless, we prove that for any finite group G the rank of does not exceed the rank of the expression in the HTW-decomposition. We also show that the HTW-decomposition predicts correct torsion for for any finite group G. Furthermore, we prove that for any degree other than the conjecture gives a correct prediction for the rank of . 相似文献
5.
6.
7.
8.
Nursel Erey 《Journal of Pure and Applied Algebra》2019,223(7):3071-3080
Let G be a -free graph with edge ideal . We show that has linear resolution for every . Also, we show that every power of the vertex cover ideal of G has linear quotients. As a result, we describe the Castelnuovo–Mumford regularity of powers of in terms of the maximum degree of G. 相似文献
9.
10.
11.
《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. 相似文献
12.
13.
14.
15.
《Discrete Mathematics》2022,345(12):113069
The toughness of a noncomplete graph G is the maximum real number t such that the ratio of to the number of components of is at least t for every cutset S of G. Determining the toughness for a given graph is NP-hard. Chvátal's toughness conjecture, stating that there exists a constant such that every graph with toughness at least is hamiltonian, is still open for general graphs. A graph is called -free if it does not contain any induced subgraph isomorphic to , the disjoint union of and two isolated vertices. In this paper, we confirm Chvátal's toughness conjecture for -free graphs by showing that every 7-tough -free graph on at least three vertices is hamiltonian. 相似文献
16.
17.
18.
19.