共查询到10条相似文献,搜索用时 265 毫秒
1.
In 1968, Vizing proposed the following conjecture: If G=(V,E) is a Δ-critical graph of order n and size m, then . This conjecture has been verified for the cases of Δ≤5. In this paper, we prove that when Δ=4. It improves the known bound for Δ=4 when n>6. 相似文献
2.
3.
A graph G is k-critical if every proper subgraph of G is (k−1)-colorable, but the graph G itself is not. We prove that every k-critical graph on n vertices has a cycle of length at least , improving a bound of Alon, Krivelevich and Seymour from 2000. Examples of Gallai from 1963 show that the bound cannot be improved to exceed . We thus settle the problem of bounding the minimal circumference of k-critical graphs, raised by Dirac in 1952 and Kelly and Kelly in 1954. 相似文献
4.
A linear coloring is a proper coloring such that each pair of color classes induces a union of disjoint paths. We study the linear list chromatic number, denoted , of sparse graphs. The maximum average degree of a graph G, denoted mad(G), is the maximum of the average degrees of all subgraphs of G. It is clear that any graph G with maximum degree Δ(G) satisfies . In this paper, we prove the following results: (1) if and Δ(G)≥3, then , and we give an infinite family of examples to show that this result is best possible; (2) if and Δ(G)≥9, then , and we give an infinite family of examples to show that the bound on cannot be increased in general; (3) if G is planar and has girth at least 5, then . 相似文献
5.
In this paper, we prove several new results on chromatic index critical graphs. We also prove that if G is a Δ(≥4)-critical graph, then
6.
This paper studies the game chromatic number and game colouring number of the square of graphs. In particular, we prove that if G is a forest of maximum degree Δ≥9, then , and there are forests G with . It is also proved that for an outerplanar graph G of maximum degree Δ, , and for a planar graph G of maximum degree Δ, . 相似文献
7.
M.A. Henning 《Discrete Mathematics》2008,308(10):1909-1920
In this paper, we continue the study of total restrained domination in graphs, a concept introduced by Telle and Proskurowksi (Algorithms for vertex partitioning problems on partial k-trees, SIAM J. Discrete Math. 10 (1997) 529-550) as a vertex partitioning problem. A set S of vertices in a graph G=(V,E) is a total restrained dominating set of G if every vertex is adjacent to a vertex in S and every vertex of V?S is adjacent to a vertex in V?S. The minimum cardinality of a total restrained dominating set of G is the total restrained domination number of G, denoted by γtr(G). Let G be a connected graph of order n with minimum degree at least 2 and with maximum degree Δ where Δ?n-2. We prove that if n?4, then and this bound is sharp. If we restrict G to a bipartite graph with Δ?3, then we improve this bound by showing that and that this bound is sharp. 相似文献
8.
If G is a connected graph with vertex set V, then the degree distance of G, D′(G), is defined as , where degw is the degree of vertex w, and d(u,v) denotes the distance between u and v. We prove the asymptotically sharp upper bound for graphs of order n and diameter d. As a corollary we obtain the bound for graphs of order n. This essentially proves a conjecture by Tomescu [I. Tomescu, Some extremal properties of the degree distance of a graph, Discrete Appl. Math. (98) (1999) 159-163]. 相似文献
9.
If G is a connected undirected simple graph on n vertices and n+c-1 edges, then G is called a c-cyclic graph. Specially, G is called a tricyclic graph if c=3. Let Δ(G) be the maximum degree of G. In this paper, we determine the structural characterizations of the c-cyclic graphs, which have the maximum spectral radii (resp. signless Laplacian spectral radii) in the class of c-cyclic graphs on n vertices with fixed maximum degree . Moreover, we prove that the spectral radius of a tricyclic graph G strictly increases with its maximum degree when , and identify the first six largest spectral radii and the corresponding graphs in the class of tricyclic graphs on n vertices. 相似文献
10.
A proper vertex coloring of a graph G is linear if the graph induced by the vertices of any two color classes is a union of vertex-disjoint paths. The linear chromatic number of G is the smallest number of colors in a linear coloring of G.Let G be a graph with maximum degree Δ(G). In this paper we prove the following results: (1) ; (2) if Δ(G)≤4; (3) if Δ(G)≤5; (4) if G is planar and Δ(G)≥52. 相似文献