共查询到20条相似文献,搜索用时 31 毫秒
1.
The -power graph of a graph is a graph with the same vertex set as , in that two vertices are adjacent if and only if, there is a path between them in of length at most . A -tree-power graph is the -power graph of a tree, a -leaf-power graph is the subgraph of some -tree-power graph induced by the leaves of the tree.We show that (1) every -tree-power graph has NLC-width at most and clique-width at most , (2) every -leaf-power graph has NLC-width at most and clique-width at most , and (3) every -power graph of a graph of tree-width has NLC-width at most , and clique-width at most . 相似文献
2.
Jeong-Hyun Kang 《Discrete Mathematics》2018,341(1):96-103
The vertices of Kneser graph are the subsets of of cardinality , two vertices are adjacent if and only if they are disjoint. The square of a graph is defined on the vertex set of with two vertices adjacent if their distance in is at most 2. Z. Füredi, in 2002, proposed the problem of determining the chromatic number of the square of the Kneser graph. The first non-trivial problem arises when . It is believed that where is a constant, and yet the problem remains open. The best known upper bounds are by Kim and Park: for 1 (Kim and Park, 2014) and for (Kim and Park, 2016). In this paper, we develop a new approach to this coloring problem by employing graph homomorphisms, cartesian products of graphs, and linear congruences integrated with combinatorial arguments. These lead to , where is a constant in , depending on . 相似文献
3.
4.
5.
Zoltán Füredi Alexandr Kostochka Ruth Luo Jacques Verstraëte 《Discrete Mathematics》2018,341(5):1253-1263
The Erd?s–Gallai Theorem states that for , any -vertex graph with no cycle of length at least has at most edges. A stronger version of the Erd?s–Gallai Theorem was given by Kopylov: If is a 2-connected -vertex graph with no cycle of length at least , then , where . Furthermore, Kopylov presented the two possible extremal graphs, one with edges and one with edges.In this paper, we complete a stability theorem which strengthens Kopylov’s result. In particular, we show that for odd and all , every -vertex 2-connected graph with no cycle of length at least is a subgraph of one of the two extremal graphs or . The upper bound for here is tight. 相似文献
6.
This paper considers a degree sum condition sufficient to imply the existence of vertex-disjoint cycles in a graph . For an integer , let be the smallest sum of degrees of independent vertices of . We prove that if has order at least and , with , then contains vertex-disjoint cycles. We also show that the degree sum condition on is sharp and conjecture a degree sum condition on sufficient to imply contains vertex-disjoint cycles for . 相似文献
7.
The vertex arboricity of a graph is the minimum number of colors the vertices can be labeled so that each color class induces a forest. It was well-known that for every planar graph . In this paper, we prove that if is a planar graph without 7-cycles. This extends a result in [A. Raspaud, W. Wang, On the vertex-arboricity of planar graphs, European J. Combin. 29 (2008) 1064–1075] that for each , planar graphs without -cycles have . 相似文献
8.
Zhi-Hong Chen 《Discrete Mathematics》2017,340(12):3104-3115
For a graph , let and let . We show that for a given number and given integers , and , if is a -connected claw-free graph of order with and its Ryjác?ek’s closure , and if where , then either is Hamiltonian or , the preimage of , can be contracted to a -edge-connected -free graph of order at most and without spanning closed trails. As applications, we prove the following for such graphs of order with sufficiently large:(i) If , , and for a given () , then either is Hamiltonian or where is a graph obtained from by replacing each of the degree 2 vertices by a (). When and , this proves a conjecture in Frydrych (2001).(ii) If , , and for a given () , then is Hamiltonian. These bounds on in (i) and (ii) are sharp. It unifies and improves several prior results on conditions involved and for the hamiltonicity of claw-free graphs. Since the number of graphs of orders at most are fixed for given , improvements to (i) or (ii) by increasing the value of are possible with the help of a computer. 相似文献
9.
Susan A. van Aardt Christoph Brause Alewyn P. Burger Marietjie Frick Arnfried Kemnitz Ingo Schiermeyer 《Discrete Mathematics》2017,340(11):2673-2677
An edge-coloured graph is called properly connected if any two vertices are connected by a path whose edges are properly coloured. The proper connection number of a connected graph denoted by , is the smallest number of colours that are needed in order to make properly connected. Our main result is the following: Let be a connected graph of order and . If , then except when and where and 相似文献
10.
11.
12.
DP-coloring of a simple graph is a generalization of list coloring, and also a generalization of signed coloring of signed graphs. It is known that for each , every planar graph without is 4-choosable. Furthermore, Jin et al. (2016) showed that for each , every signed planar graph without is signed 4-choosable. In this paper, we show that for each , every planar graph without is 4-DP-colorable, which is an extension of the above results. 相似文献
13.
14.
15.
16.
17.
A note on degree sum conditions for 2-factors with a prescribed number of cycles in bipartite graphs
Let be a balanced bipartite graph of order , and let be the minimum degree sum of two non-adjacent vertices in different partite sets of . In 1963, Moon and Moser proved that if , then is hamiltonian. In this note, we show that if is a positive integer, then the Moon–Moser condition also implies the existence of a 2-factor with exactly cycles for sufficiently large graphs. In order to prove this, we also give a condition for the existence of vertex-disjoint alternating cycles with respect to a chosen perfect matching in . 相似文献
18.
19.
Let be a set of at least two vertices in a graph . A subtree of is a -Steiner tree if . Two -Steiner trees and are edge-disjoint (resp. internally vertex-disjoint) if (resp. and ). Let (resp. ) be the maximum number of edge-disjoint (resp. internally vertex-disjoint) -Steiner trees in , and let (resp. ) be the minimum (resp. ) for ranges over all -subset of . Kriesell conjectured that if for any , then . He proved that the conjecture holds for . In this paper, we give a short proof of Kriesell’s Conjecture for , and also show that (resp. ) if (resp. ) in , where . Moreover, we also study the relation between and , where is the line graph of . 相似文献
20.
For a subgraph of , let be the maximum number of vertices of that are pairwise distance at least three in . In this paper, we prove three theorems. Let be a positive integer, and let be a subgraph of an -connected claw-free graph . We prove that if , then either can be covered by a cycle in , or there exists a cycle in such that . This result generalizes the result of Broersma and Lu that has a cycle covering all the vertices of if . We also prove that if , then either can be covered by a path in , or there exists a path in such that . By using the second result, we prove the third result. For a tree , a vertex of with degree one is called a leaf of . For an integer , a tree which has at most leaves is called a -ended tree. We prove that if , then has a -ended tree covering all the vertices of . This result gives a positive answer to the conjecture proposed by Kano et al. (2012). 相似文献