共查询到20条相似文献,搜索用时 390 毫秒
1.
2.
3.
4.
5.
6.
The distinguishing index of a graph is the least cardinal number such that has an edge-coloring with colors, which is preserved only by the trivial automorphism. We prove a general upper bound for any connected infinite graph with finite maximum degree . This is in contrast with finite graphs since for every there exist infinitely many connected, finite graphs with . We also give examples showing that this bound is sharp for any maximum degree . 相似文献
7.
8.
9.
Let be an integer with and be a connected -uniform hypergraph with edges. By refining the broken cycle theorem for hypergraphs, we show that if , then the -list assignment of admitting the fewest colorings is the constant list assignment. This extends the previous results of Donner, Thomassen, and the current authors for graphs. 相似文献
10.
11.
12.
Richard C. Brewster Jae-Baek Lee Benjamin Moore Jonathan A. Noel Mark Siggers 《Journal of Graph Theory》2020,94(3):398-420
We say that a graph strongly arrows a pair of graphs and write if any coloring of its edges with red and blue leads to either a red or a blue appearing as induced subgraphs of . The induced Ramsey number, , is defined as . We consider the connection between the induced Ramsey number for a pair of two connected graphs and the induced Ramsey number for multiple copies of these graphs , where denotes the pairwise vertex-disjoint union of copies of . It is easy to see that if , then . This implies that For several specific graphs, such as a path on three vertices vs a complete multipartite graph, a matching vs a complete graph, or a matching vs another matching, it is known that the above inequality is tight. On the other hand, the inequality is also strict for some graphs. However, even in the simplest case when is an edge and , it is not known for what and for what the above inequality is tight. We show that it is tight if is connected and is at least as large as the order of . In addition, we make further progress in determining induced Ramsey numbers for multiple copies of graphs, such as paths and triangles. 相似文献
13.
14.
Daniel W. Cranston 《Journal of Graph Theory》2019,92(4):460-487
A graph is -choosable if given any list assignment with for each there exists a function such that and for all , and whenever vertices and are adjacent . Meng, Puleo, and Zhu conjectured a characterization of (4,2)-choosable graphs. We prove their conjecture. 相似文献
15.
16.
Win conjectured that a graph on vertices contains disjoint perfect matchings, if the degree sum of any two nonadjacent vertices is at least , where is even and . In this paper, we prove that Win's conjecture is true for , where is sufficiently large. To show this result, we prove a theorem on -factor in a graph under some Ore-type condition. Our main tools include Tutte's -factor theorem, the Karush-Kuhn-Tucker theorem on convex optimization and the solution to the long-standing 1-factor decomposition conjecture. 相似文献
17.
18.
19.
20.
A graph with at least vertices is said to be distance -extendable if, for any matching of with edges in which the edges lie at distance at least pairwise, there exists a perfect matching of containing . In this paper we prove that every 5-connected triangulation on the projective plane of even order is distance 3 7-extendable and distance 4 -extendable for any . 相似文献