Увійти

Готові списки джерел за темами / Rainbow subgraph / Статті в журналах

Щоб переглянути інші типи публікацій з цієї теми, перейдіть за посиланням: Rainbow subgraph.

Статті в журналах з теми "Rainbow subgraph"

Автор: Grafiati

Опубліковано: 25 травня 2024

Оформте джерело за APA, MLA, Chicago, Harvard та іншими стилями

Оберіть тип джерела:

Ознайомтеся з топ-50 статей у журналах для дослідження на тему "Rainbow subgraph".

Біля кожної праці в переліку літератури доступна кнопка «Додати до бібліографії». Скористайтеся нею – і ми автоматично оформимо бібліографічне посилання на обрану працю в потрібному вам стилі цитування: APA, MLA, «Гарвард», «Чикаго», «Ванкувер» тощо.

Також ви можете завантажити повний текст наукової публікації у форматі «.pdf» та прочитати онлайн анотацію до роботи, якщо відповідні параметри наявні в метаданих.

Переглядайте статті в журналах для різних дисциплін та оформлюйте правильно вашу бібліографію.

1

Axenovich, Maria, Tao Jiang, and Z. Tuza. "Local Anti-Ramsey Numbers of Graphs." Combinatorics, Probability and Computing 12, no. 5-6 (November 2003): 495–511. http://dx.doi.org/10.1017/s0963548303005868.

Повний текст джерела

Анотація:

A subgraph H in an edge-colouring is properly coloured if incident edges of H are assigned different colours, and H is rainbow if no two edges of H are assigned the same colour. We study properly coloured subgraphs and rainbow subgraphs forced in edge-colourings of complete graphs in which each vertex is incident to a large number of colours.

Стилі APA, Harvard, Vancouver, ISO та ін.

2

Lestari, Dia, and I. Ketut Budayasa. "BILANGAN KETERHUBUNGAN PELANGI PADA PEWARNAAN-SISI GRAF." MATHunesa: Jurnal Ilmiah Matematika 8, no. 1 (April 23, 2020): 25–34. http://dx.doi.org/10.26740/mathunesa.v8n1.p25-34.

Повний текст джерела

Анотація:

Let be a graph. An edge-coloring of is a function , where is a set of colors. Respect to a subgraph of is called a rainbow subgraph if all edges of get different colors. Graph is called rainbow connected if for every two distinct vertices of is joined by a rainbow path. The rainbow connection number of , denoted by , is the minimum number of colors needed in coloring all edges of such that is a rainbow connected. The main problem considered in this thesis is determining the rainbow connection number of graph. In this thesis, we determine the exact value of the rainbow connection number of some classes of graphs such as Cycles, Complete graph, and Tree. We also determining the lower bound and upper bound for the rainbow connection number of graph. Keywords: Rainbow Connection Number, Graph, Edge-Coloring on Graph.

Стилі APA, Harvard, Vancouver, ISO та ін.

3

KOSTOCHKA, ALEXANDR, and MATTHEW YANCEY. "Large Rainbow Matchings in Edge-Coloured Graphs." Combinatorics, Probability and Computing 21, no. 1-2 (February 2, 2012): 255–63. http://dx.doi.org/10.1017/s0963548311000605.

Повний текст джерела

Анотація:

Arainbow subgraphof an edge-coloured graph is a subgraph whose edges have distinct colours. Thecolour degreeof a vertexvis the number of different colours on edges incident withv. Wang and Li conjectured that fork≥ 4, every edge-coloured graph with minimum colour degreekcontains a rainbow matching of size at least ⌈k/2⌉. A properly edge-colouredK4has no such matching, which motivates the restrictionk≥ 4, but Li and Xu proved the conjecture for all other properly coloured complete graphs. LeSaulnier, Stocker, Wenger and West showed that a rainbow matching of size ⌊k/2⌋ is guaranteed to exist, and they proved several sufficient conditions for a matching of size ⌈k/2⌉. We prove the conjecture in full.

Стилі APA, Harvard, Vancouver, ISO та ін.

4

Hüffner, Falk, Christian Komusiewicz, Rolf Niedermeier, and Martin Rötzschke. "The Parameterized Complexity of the Rainbow Subgraph Problem." Algorithms 8, no. 1 (February 27, 2015): 60–81. http://dx.doi.org/10.3390/a8010060.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

5

Matos Camacho, Stephan, Ingo Schiermeyer, and Zsolt Tuza. "Approximation algorithms for the minimum rainbow subgraph problem." Discrete Mathematics 310, no. 20 (October 2010): 2666–70. http://dx.doi.org/10.1016/j.disc.2010.03.032.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

6

Koch, Maria, Stephan Matos Camacho, and Ingo Schiermeyer. "Algorithmic approaches for the minimum rainbow subgraph problem." Electronic Notes in Discrete Mathematics 38 (December 2011): 765–70. http://dx.doi.org/10.1016/j.endm.2011.10.028.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

7

Gyárfás, András, Jenő Lehel, and Richard H. Schelp. "Finding a monochromatic subgraph or a rainbow path." Journal of Graph Theory 54, no. 1 (2006): 1–12. http://dx.doi.org/10.1002/jgt.20179.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

8

LOH, PO-SHEN, and BENNY SUDAKOV. "Constrained Ramsey Numbers." Combinatorics, Probability and Computing 18, no. 1-2 (March 2009): 247–58. http://dx.doi.org/10.1017/s0963548307008875.

Повний текст джерела

Анотація:

For two graphs S and T, the constrained Ramsey number f(S, T) is the minimum n such that every edge colouring of the complete graph on n vertices (with any number of colours) has a monochromatic subgraph isomorphic to S or a rainbow subgraph isomorphic to T. Here, a subgraph is said to be rainbow if all of its edges have different colours. It is an immediate consequence of the Erdős–Rado Canonical Ramsey Theorem that f(S, T) exists if and only if S is a star or T is acyclic. Much work has been done to determine the rate of growth of f(S, T) for various types of parameters. When S and T are both trees having s and t edges respectively, Jamison, Jiang and Ling showed that f(S, T) ≤ O(st2) and conjectured that it is always at most O(st). They also mentioned that one of the most interesting open special cases is when T is a path. In this paper, we study this case and show that f(S, Pt) = O(st log t), which differs only by a logarithmic factor from the conjecture. This substantially improves the previous bounds for most values of s and t.

Стилі APA, Harvard, Vancouver, ISO та ін.

9

Schiermeyer, Ingo. "On the minimum rainbow subgraph number of a graph." Ars Mathematica Contemporanea 6, no. 1 (June 1, 2012): 83–88. http://dx.doi.org/10.26493/1855-3974.246.94d.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

10

Katrenič, Ján, and Ingo Schiermeyer. "Improved approximation bounds for the minimum rainbow subgraph problem." Information Processing Letters 111, no. 3 (January 2011): 110–14. http://dx.doi.org/10.1016/j.ipl.2010.11.005.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

11

Xiang, Changyuan, Yongxin Lan, Qinghua Yan, and Changqing Xu. "The Outer-Planar Anti-Ramsey Number of Matchings." Symmetry 14, no. 6 (June 16, 2022): 1252. http://dx.doi.org/10.3390/sym14061252.

Повний текст джерела

Анотація:

A subgraph H of an edge-colored graph G is called rainbow if all of its edges have different colors. Let ar(G,H) denote the maximum positive integer t, such that there is a t-edge-colored graph G without any rainbow subgraph H. We denote by kK2 a matching of size k and On the class of all maximal outer-planar graphs on n vertices, respectively. The outer-planar anti-Ramsey number of graph H, denoted by ar(On,H), is defined as max{ar(On,H)|On∈On}. It seems nontrivial to determine the exact values for ar(On,H) because most maximal outer-planar graphs are asymmetry. In this paper, we obtain that ar(On,kK2)≤n+3k−8 for all n≥2k and k≥6, which improves the existing upper bound for ar(On,kK2), and prove that ar(On,kK2)=n+2k−5 for n=2k and k≥5. We also obtain that ar(On,6K2)=n+6 for all n≥29.

Стилі APA, Harvard, Vancouver, ISO та ін.

12

Yuan, Chen, and Haibin Kan. "Revisiting a randomized algorithm for the minimum rainbow subgraph problem." Theoretical Computer Science 593 (August 2015): 154–59. http://dx.doi.org/10.1016/j.tcs.2015.05.042.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

13

Popa, Alexandru. "Better lower and upper bounds for the minimum rainbow subgraph problem." Theoretical Computer Science 543 (July 2014): 1–8. http://dx.doi.org/10.1016/j.tcs.2014.05.008.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

14

SUN, YUEFANG. "The (3, l)-Rainbow Edge-Index of Cartesian Product Graphs." Journal of Interconnection Networks 17, no. 03n04 (September 2017): 1741009. http://dx.doi.org/10.1142/s0219265917410092.

Повний текст джерела

Анотація:

For a graph G and a vertex subset [Formula: see text] of at least two vertices, an S-tree is a subgraph T of G that is a tree with [Formula: see text]. Two S-trees are said to be edge-disjoint if they have no common edge. Let [Formula: see text] denote the maximum number of edge-disjoint S-trees in G. For an integer K with [Formula: see text], the generalized k-edge-connectivity is defined as [Formula: see text]. An S-tree in an edge-colored graph is rainbow if no two edges of it are assigned the same color. Let [Formula: see text] and l be integers with [Formula: see text], the [Formula: see text]-rainbow edge-index [Formula: see text] of G is the smallest number of colors needed in an edge-coloring of G such that for every set S of k vertices of G, there exist l edge-disjoint rainbow S-trees.In this paper, we study the [Formula: see text]-rainbow edge-index of Cartesian product graphs and get a sharp upper bound for [Formula: see text] , where G and H are connected graphs with orders at least three, and [Formula: see text] denotes the Cartesian product of G and H.

Стилі APA, Harvard, Vancouver, ISO та ін.

15

Mao, Yaping, and Yongtang Shi. "The complexity of determining the vertex-rainbow index of graphs." Discrete Mathematics, Algorithms and Applications 07, no. 04 (December 2015): 1550047. http://dx.doi.org/10.1142/s1793830915500470.

Повний текст джерела

Анотація:

The concept of the [Formula: see text]-rainbow index of a network comes from the communication of information between agencies of government, which was introduced by Chartrand et al. in 2010. As a natural counterpart of the [Formula: see text]-rainbow index, the concept of [Formula: see text]-vertex-rainbow index was also introduced. For a graph [Formula: see text] and a set [Formula: see text] of at least two vertices, an [Formula: see text]-Steiner tree or a Steiner tree connecting [Formula: see text] (or simply, an [Formula: see text]-tree) is such a subgraph [Formula: see text] of [Formula: see text] that is a tree with [Formula: see text]. For [Formula: see text] and [Formula: see text], an [Formula: see text]-Steiner tree [Formula: see text] is said to be a vertex-rainbow [Formula: see text]-tree if the vertices of [Formula: see text] have distinct colors. For a fixed integer [Formula: see text] with [Formula: see text], the vertex-coloring [Formula: see text] of [Formula: see text] is called a [Formula: see text]-vertex-rainbow coloring if for every [Formula: see text]-subset [Formula: see text] of [Formula: see text] there exists a vertex-rainbow [Formula: see text]-tree. In this case, [Formula: see text] is called vertex-rainbow [Formula: see text]-tree-connected. The minimum number of colors that are needed in a [Formula: see text]-vertex-rainbow coloring of [Formula: see text] is called the [Formula: see text]-vertex-rainbow index of [Formula: see text], denoted by [Formula: see text]. In this paper, we study the complexity of determining the [Formula: see text]-vertex-rainbow index of a graph and prove that computing [Formula: see text] is [Formula: see text]-Hard. Moreover, we show that it is [Formula: see text]-Complete to decide whether [Formula: see text]. We also prove that the following problem is [Formula: see text]-Complete: Given a vertex-colored graph [Formula: see text], check whether the given coloring makes [Formula: see text] vertex-rainbow [Formula: see text]-tree-connected.

Стилі APA, Harvard, Vancouver, ISO та ін.

16

Tirodkar, Sumedh, and Sundar Vishwanathan. "On the Approximability of the Minimum Rainbow Subgraph Problem and Other Related Problems." Algorithmica 79, no. 3 (January 11, 2017): 909–24. http://dx.doi.org/10.1007/s00453-017-0278-4.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

17

Goddard, Wayne, and Honghai Xu. "Vertex colorings without rainbow subgraphs." Discussiones Mathematicae Graph Theory 36, no. 4 (2016): 989. http://dx.doi.org/10.7151/dmgt.1896.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

18

Cui, Qing, Qinghai Liu, Colton Magnant, and Akira Saito. "Implications in rainbow forbidden subgraphs." Discrete Mathematics 344, no. 4 (April 2021): 112267. http://dx.doi.org/10.1016/j.disc.2020.112267.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

19

Holub, Přemysl, Zdeněk Ryjáček, Ingo Schiermeyer, and Petr Vrána. "Rainbow connection and forbidden subgraphs." Discrete Mathematics 338, no. 10 (October 2015): 1706–13. http://dx.doi.org/10.1016/j.disc.2014.08.008.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

20

Gorgol, Izolda. "Avoiding rainbow 2-connected subgraphs." Open Mathematics 15, no. 1 (April 17, 2017): 393–97. http://dx.doi.org/10.1515/math-2017-0035.

Повний текст джерела

Анотація:

Abstract While defining the anti-Ramsey number Erdős, Simonovits and Sós mentioned that the extremal colorings may not be unique. In the paper we discuss the uniqueness of the colorings, generalize the idea of their construction and show how to use it to construct the colorings of the edges of complete split graphs avoiding rainbow 2-connected subgraphs. These colorings give the lower bounds for adequate anti-Ramsey numbers.

Стилі APA, Harvard, Vancouver, ISO та ін.

21

Fujita, Shinya, and Colton Magnant. "Forbidden Rainbow Subgraphs That Force Large Highly Connected Monochromatic Subgraphs." SIAM Journal on Discrete Mathematics 27, no. 3 (January 2013): 1625–37. http://dx.doi.org/10.1137/120896906.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

22

Li, Wenjing, Xueliang Li, and Jingshu Zhang. "Rainbow vertex-connection and forbidden subgraphs." Discussiones Mathematicae Graph Theory 38, no. 1 (2018): 143. http://dx.doi.org/10.7151/dmgt.2004.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

23

Li, Wenjing, Xueliang Li, and Jingshu Zhang. "3-Rainbow Index and Forbidden Subgraphs." Graphs and Combinatorics 33, no. 4 (May 22, 2017): 999–1008. http://dx.doi.org/10.1007/s00373-017-1783-6.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

24

Barrus, Michael D., Michael Ferrara, Jennifer Vandenbussche, and Paul S. Wenger. "Colored Saturation Parameters for Rainbow Subgraphs." Journal of Graph Theory 86, no. 4 (March 8, 2017): 375–86. http://dx.doi.org/10.1002/jgt.22132.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

25

Kisielewicz, Andrzej, and Marek Szykuła. "Rainbow Induced Subgraphs in Proper Vertex Colorings." Fundamenta Informaticae 111, no. 4 (2011): 437–51. http://dx.doi.org/10.3233/fi-2011-572.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

26

Axenovich, Maria, and Perry Iverson. "Edge-colorings avoiding rainbow and monochromatic subgraphs." Discrete Mathematics 308, no. 20 (October 2008): 4710–23. http://dx.doi.org/10.1016/j.disc.2007.08.092.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

27

Wagner, Adam Zsolt. "Large Subgraphs in Rainbow-Triangle Free Colorings." Journal of Graph Theory 86, no. 2 (March 7, 2017): 141–48. http://dx.doi.org/10.1002/jgt.22117.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

28

Rödl, Vojtech, and Zsolt Tuza. "Rainbow subgraphs in properly edge-colored graphs." Random Structures & Algorithms 3, no. 2 (1992): 175–82. http://dx.doi.org/10.1002/rsa.3240030207.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

29

Ma, Zhiqiang, Yaping Mao, Ingo Schiermeyer, and Meiqin Wei. "Complete bipartite graphs without small rainbow subgraphs." Discrete Applied Mathematics 346 (March 2024): 248–62. http://dx.doi.org/10.1016/j.dam.2023.12.020.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

30

Alon, Noga, Tao Jiang, Zevi Miller, and Dan Pritikin. "Properly colored subgraphs and rainbow subgraphs in edge-colorings with local constraints." Random Structures and Algorithms 23, no. 4 (November 11, 2003): 409–33. http://dx.doi.org/10.1002/rsa.10102.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

31

Li, Xihe, and Ligong Wang. "Forbidden rainbow subgraphs that force large monochromatic or multicolored k-connected subgraphs." Discrete Applied Mathematics 285 (October 2020): 18–29. http://dx.doi.org/10.1016/j.dam.2020.05.004.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

32

Goddard, Wayne, and Robert Melville. "Coloring subgraphs with restricted amounts of hues." Open Mathematics 15, no. 1 (September 22, 2017): 1171–80. http://dx.doi.org/10.1515/math-2017-0098.

Повний текст джерела

Анотація:

Abstract We consider vertex colorings where the number of colors given to specified subgraphs is restricted. In particular, given some fixed graph F and some fixed set A of positive integers, we consider (not necessarily proper) colorings of the vertices of a graph G such that, for every copy of F in G, the number of colors it receives is in A. This generalizes proper colorings, defective coloring, and no-rainbow coloring, inter alia. In this paper we focus on the case that A is a singleton set. In particular, we investigate the colorings where the graph F is a star or is 1-regular.

Стилі APA, Harvard, Vancouver, ISO та ін.

33

Czap, Július. "Rainbow subgraphs in edge-colored planar and outerplanar graphs." Discrete Mathematics Letters 12 (June 23, 2023): 73–77. http://dx.doi.org/10.47443/dml.2023.048.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

34

Liu, Yuchen, and Yaojun Chen. "Rainbow subgraphs in Hamiltonian cycle decompositions of complete graphs." Discrete Mathematics 346, no. 8 (August 2023): 113479. http://dx.doi.org/10.1016/j.disc.2023.113479.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

35

Klavžar, Sandi, and Gašper Mekiš. "On the rainbow connection of Cartesian products and their subgraphs." Discussiones Mathematicae Graph Theory 32, no. 4 (2012): 783. http://dx.doi.org/10.7151/dmgt.1644.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

36

Brousek, Jan, Přemysl Holub, Zdeněk Ryjáček, and Petr Vrána. "Finite families of forbidden subgraphs for rainbow connection in graphs." Discrete Mathematics 339, no. 9 (September 2016): 2304–12. http://dx.doi.org/10.1016/j.disc.2016.02.015.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

37

Bradshaw, Peter. "Rainbow spanning trees in random subgraphs of dense regular graphs." Discrete Mathematics 347, no. 6 (June 2024): 113960. http://dx.doi.org/10.1016/j.disc.2024.113960.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

38

Ding, Jili, Hong Bian, and Haizheng Yu. "Anti-Ramsey Numbers in Complete k-Partite Graphs." Mathematical Problems in Engineering 2020 (September 7, 2020): 1–5. http://dx.doi.org/10.1155/2020/5136104.

Повний текст джерела

Анотація:

The anti-Ramsey number ARG,H is the maximum number of colors in an edge-coloring of G such that G contains no rainbow subgraphs isomorphic to H. In this paper, we discuss the anti-Ramsey numbers ARKp1,p2,…,pk,Tn, ARKp1,p2,…,pk,ℳ, and ARKp1,p2,…,pk,C of Kp1,p2,…,pk, where Tn,ℳ, and C denote the family of all spanning trees, the family of all perfect matchings, and the family of all Hamilton cycles in Kp1,p2,…,pk, respectively.

Стилі APA, Harvard, Vancouver, ISO та ін.

39

Jahanbekam, Sogol, and Douglas B. West. "Rainbow Spanning Subgraphs of Small Diameter in Edge-Colored Complete Graphs." Graphs and Combinatorics 32, no. 2 (June 6, 2015): 707–12. http://dx.doi.org/10.1007/s00373-015-1588-4.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

40

Alon, Noga, Alexey Pokrovskiy, and Benny Sudakov. "Random subgraphs of properly edge-coloured complete graphs and long rainbow cycles." Israel Journal of Mathematics 222, no. 1 (October 2017): 317–31. http://dx.doi.org/10.1007/s11856-017-1592-x.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

41

Holub, Přemysl, Zdeněk Ryjáček, and Ingo Schiermeyer. "On forbidden subgraphs and rainbow connection in graphs with minimum degree 2." Discrete Mathematics 338, no. 3 (March 2015): 1–8. http://dx.doi.org/10.1016/j.disc.2014.10.006.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

42

Cano, Pilar, Guillem Perarnau, and Oriol Serra. "Rainbow spanning subgraphs in bounded edge–colourings of graphs with large minimum degree." Electronic Notes in Discrete Mathematics 61 (August 2017): 199–205. http://dx.doi.org/10.1016/j.endm.2017.06.039.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

43

Jahanbekam, Sogol, and Douglas B. West. "Anti-Ramsey Problems for t Edge-Disjoint Rainbow Spanning Subgraphs: Cycles, Matchings, or Trees." Journal of Graph Theory 82, no. 1 (June 26, 2015): 75–89. http://dx.doi.org/10.1002/jgt.21888.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

44

Jia, Yuxing, Mei Lu, and Yi Zhang. "Anti-Ramsey Problems in Complete Bipartite Graphs for t Edge-Disjoint Rainbow Spanning Subgraphs: Cycles and Matchings." Graphs and Combinatorics 35, no. 5 (June 27, 2019): 1011–21. http://dx.doi.org/10.1007/s00373-019-02053-y.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

45

Yuster, Raphael. "Rainbow $H$-factors." Electronic Journal of Combinatorics 13, no. 1 (February 15, 2006). http://dx.doi.org/10.37236/1039.

Повний текст джерела

Анотація:

An $H$-factor of a graph $G$ is a spanning subgraph of $G$ whose connected components are isomorphic to $H$. Given a properly edge-colored graph $G$, a rainbow $H$-subgraph of $G$ is an $H$-subgraph of $G$ whose edges have distinct colors. A rainbow $H$-factor is an $H$-factor whose components are rainbow $H$-subgraphs. The following result is proved. If $H$ is any fixed graph with $h$ vertices then every properly edge-colored graph with $hn$ vertices and minimum degree $(1-1/\chi(H))hn+o(n)$ has a rainbow $H$-factor.

Стилі APA, Harvard, Vancouver, ISO та ін.

46

Ehard, Stefan, Stefan Glock, and Felix Joos. "A rainbow blow-up lemma for almost optimally bounded edge-colourings." Forum of Mathematics, Sigma 8 (2020). http://dx.doi.org/10.1017/fms.2020.38.

Повний текст джерела

Анотація:

Abstract A subgraph of an edge-coloured graph is called rainbow if all its edges have different colours. We prove a rainbow version of the blow-up lemma of Komlós, Sárközy, and Szemerédi that applies to almost optimally bounded colourings. A corollary of this is that there exists a rainbow copy of any bounded-degree spanning subgraph H in a quasirandom host graph G, assuming that the edge-colouring of G fulfills a boundedness condition that is asymptotically best possible. This has many applications beyond rainbow colourings: for example, to graph decompositions, orthogonal double covers, and graph labellings.

Стилі APA, Harvard, Vancouver, ISO та ін.

47

LeSaulnier, Timothy D., Christopher Stocker, Paul S. Wenger, and Douglas B. West. "Rainbow Matching in Edge-Colored Graphs." Electronic Journal of Combinatorics 17, no. 1 (May 14, 2010). http://dx.doi.org/10.37236/475.

Повний текст джерела

Анотація:

A rainbow subgraph of an edge-colored graph is a subgraph whose edges have distinct colors. The color degree of a vertex $v$ is the number of different colors on edges incident to $v$. Wang and Li conjectured that for $k\geq 4$, every edge-colored graph with minimum color degree at least $k$ contains a rainbow matching of size at least $\left\lceil k/2 \right\rceil$. We prove the slightly weaker statement that a rainbow matching of size at least $\left\lfloor k/2 \right\rfloor$ is guaranteed. We also give sufficient conditions for a rainbow matching of size at least $\left\lceil k/2 \right\rceil$ that fail to hold only for finitely many exceptions (for each odd $k$).

Стилі APA, Harvard, Vancouver, ISO та ін.

48

He, Zhen, Peter Frankl, Ervin Győri, Zequn Lv, Nika Salia, Casey Tompkins, Kitti Varga, and Xiutao Zhu. "Extremal Results for Graphs Avoiding a Rainbow Subgraph." Electronic Journal of Combinatorics 31, no. 1 (January 26, 2024). http://dx.doi.org/10.37236/11676.

Повний текст джерела

Анотація:

We say that $k$ graphs $G_1,G_2,\dots,G_k$ on a common vertex set of size $n$ contain a rainbow copy of a graph $H$ if their union contains a copy of $H$ with each edge belonging to a distinct $G_i$. We provide a counterexample to a conjecture of Frankl on the maximum product of the sizes of the edge sets of three graphs avoiding a rainbow triangle. We propose an alternative conjecture, which we prove under the additional assumption that the union of the three graphs is complete. Furthermore, we determine the maximum product of the sizes of the edge sets of three graphs or four graphs avoiding a rainbow path of length three.

Стилі APA, Harvard, Vancouver, ISO та ін.

49

Axenovich, Maria, and Ryan Martin. "Avoiding Rainbow Induced Subgraphs in Vertex-Colorings." Electronic Journal of Combinatorics 15, no. 1 (January 14, 2008). http://dx.doi.org/10.37236/736.

Повний текст джерела

Анотація:

For a fixed graph $H$ on $k$ vertices, and a graph $G$ on at least $k$ vertices, we write $G\longrightarrow H$ if in any vertex-coloring of $G$ with $k$ colors, there is an induced subgraph isomorphic to $H$ whose vertices have distinct colors. In other words, if $G\longrightarrow H$ then a totally multicolored induced copy of $H$ is unavoidable in any vertex-coloring of $G$ with $k$ colors. In this paper, we show that, with a few notable exceptions, for any graph $H$ on $k$ vertices and for any graph $G$ which is not isomorphic to $H$, $G\not\!\!\longrightarrow H$. We explicitly describe all exceptional cases. This determines the induced vertex-anti-Ramsey number for all graphs and shows that totally multicolored induced subgraphs are, in most cases, easily avoidable.

Стилі APA, Harvard, Vancouver, ISO та ін.

50

Correia, David Munh, Alexey Pokrovskiy, and Benny Sudakov. "Short Proofs of Rainbow Matchings Results." International Mathematics Research Notices, July 17, 2022. http://dx.doi.org/10.1093/imrn/rnac180.

Повний текст джерела

Анотація:

Abstract A subgraph of an edge-coloured graph is called rainbow if all its edges have distinct colours. The study of rainbow subgraphs goes back to the work of Euler on Latin squares and has been the focus of extensive research ever since. Many conjectures in this area roughly say that “every edge coloured graph of a certain type contains a rainbow matching using every colour.” In this paper we introduce a versatile “sampling trick,” which allows us to asymptotically solve some well-known conjectures and to obtain short proofs of old results. In particular: $\bullet $ We give the first asymptotic proof of the “non-bipartite” Aharoni–Berger conjecture, solving two conjectures of Aharoni, Berger, Chudnovsky, and Zerbib. $\bullet $ We give a very short asymptotic proof of Grinblat’s conjecture (first obtained by Clemens, Ehrenmüller, and Pokrovskiy). Furthermore, we obtain a new asymptotically tight bound for Grinblat’s problem as a function of edge multiplicity of the corresponding multigraph. $\bullet $ We give the first asymptotic proof of a 30-year-old conjecture of Alspach. $\bullet $ We give a simple proof of Pokrovskiy’s asymptotic version of the Aharoni–Berger conjecture with greatly improved error term.

Стилі APA, Harvard, Vancouver, ISO та ін.

Ми пропонуємо знижки на всі преміум-плани для авторів, чиї праці увійшли до тематичних добірок літератури. Зв'яжіться з нами, щоб отримати унікальний промокод!