Articles de revues : « Edge-colored graph »

1

Ma, Huawen. « Maximum Colored Cuts in Edge-Colored Complete Graphs ». Journal of Mathematics 2022 (7 juillet 2022) : 1–4. http://dx.doi.org/10.1155/2022/9515498.

Texte intégral

Résumé :

Max-Cut problem is one of the classical problems in graph theory and has been widely studied in recent years. Maximum colored cut problem is a more general problem, which is to find a bipartition of a given edge-colored graph maximizing the number of colors in edges going across the bipartition. In this work, we gave some lower bounds on maximum colored cuts in edge-colored complete graphs containing no rainbow triangles or properly colored 4-cycles.

Styles APA, Harvard, Vancouver, ISO, etc.

2

Arora, Ajay, Eddie Cheng et Colton Magnant. « Proper Coloring Distance in Edge-Colored Cartesian Products of Complete Graphs and Cycles ». Parallel Processing Letters 29, n^o 04 (décembre 2019) : 1950016. http://dx.doi.org/10.1142/s0129626419500166.

Texte intégral

Résumé :

An path that is edge-colored is called proper if no two consecutive edges receive the same color. A general graph that is edge-colored is called properly connected if, for every pair of vertices in the graph, there exists a properly colored path from one to the other. Given two vertices u and v in a properly connected graph G, the proper distance is the length of the shortest properly colored path from u to v. By considering a specific class of colorings that are properly connected for Cartesian products of complete and cyclic graphs, we present results on the proper distance between all pairs of vertices in the graph.

Styles APA, Harvard, Vancouver, ISO, etc.

3

Guo, Zhiwei, Hajo Broersma, Ruonan Li et Shenggui Zhang. « Some algorithmic results for finding compatible spanning circuits in edge-colored graphs ». Journal of Combinatorial Optimization 40, n^o 4 (4 septembre 2020) : 1008–19. http://dx.doi.org/10.1007/s10878-020-00644-7.

Texte intégral

Résumé :

Abstract A compatible spanning circuit in a (not necessarily properly) edge-colored graph G is a closed trail containing all vertices of G in which any two consecutively traversed edges have distinct colors. Sufficient conditions for the existence of extremal compatible spanning circuits (i.e., compatible Hamilton cycles and Euler tours), and polynomial-time algorithms for finding compatible Euler tours have been considered in previous literature. More recently, sufficient conditions for the existence of more general compatible spanning circuits in specific edge-colored graphs have been established. In this paper, we consider the existence of (more general) compatible spanning circuits from an algorithmic perspective. We first show that determining whether an edge-colored connected graph contains a compatible spanning circuit is an NP-complete problem. Next, we describe two polynomial-time algorithms for finding compatible spanning circuits in edge-colored complete graphs. These results in some sense give partial support to a conjecture on the existence of compatible Hamilton cycles in edge-colored complete graphs due to Bollobás and Erdős from the 1970s.

Styles APA, Harvard, Vancouver, ISO, etc.

4

Jin, Zemin, Kun Ye, He Chen et Yuefang Sun. « Large rainbow matchings in semi-strong edge-colorings of graphs ». Discrete Mathematics, Algorithms and Applications 10, n^o 02 (avril 2018) : 1850021. http://dx.doi.org/10.1142/s1793830918500210.

Texte intégral

Résumé :

The lower bounds for the size of maximum rainbow matching in properly edge-colored graphs have been studied deeply during the last decades. An edge-coloring of a graph [Formula: see text] is called a strong edge-coloring if each path of length at most three is rainbow. Clearly, the strong edge-coloring is a natural generalization of the proper one. Recently, Babu et al. considered the problem in the strongly edge-colored graphs. In this paper, we introduce a semi-strong edge-coloring of graphs and consider the existence of large rainbow matchings in it.

Styles APA, Harvard, Vancouver, ISO, etc.

5

Razumovsky, P. V., et M. B. Abrosimov. « THE MINIMAL VERTEX EXTENSIONS FOR COLORED COMPLETE GRAPHS ». Bulletin of the South Ural State University series "Mathematics. Mechanics. Physics" 13, n^o 4 (2021) : 77–89. http://dx.doi.org/10.14529/mmph210409.

Texte intégral

Résumé :

The article proposes the results of the search for minimal vertex extensions of undirected colored complete graphs. The research topic is related to the modelling of full fault tolerant technical systems with a different type of their objects in the terminology of graph theory. Let a technical system be Σ, then there is a graph G(Σ), which vertices reflects system’s objects and edges reflects connections between these objects. Type of each object reflected in a mapping of some color from F = {1,2…,i} to the corresponding vertex. System’s Σ vertex extension is a graph G(Σ) which contains additional vertices. System reflected by graph G(Σ) can work even if there are k faults of its objects. Complete graph is a graph where each two vertices have an edge between them. Complete graphs have no edge extensions because there is no way to add additional edge to the graph with a maximum number of edges. In other words, the system reflected by some complete graph cannot be able to resist connection faults. Therefore the article research is focused on vertex extensions only. There is a description of vertex extensions existence condition for those colored complete graphs. This paper considers generating schemes for such minimal vertex extensions along with formulas, which allows to calculate number of additional edges to have an ability to construct minimal vertex extension.

Styles APA, Harvard, Vancouver, ISO, etc.

6

DI GIACOMO, EMILIO, GIUSEPPE LIOTTA et FRANCESCO TROTTA. « ON EMBEDDING A GRAPH ON TWO SETS OF POINTS ». International Journal of Foundations of Computer Science 17, n^o 05 (octobre 2006) : 1071–94. http://dx.doi.org/10.1142/s0129054106004273.

Texte intégral

Résumé :

Let R and B be two sets of points such that the points of R are colored red and the points of B are colored blue. Let G be a planar graph such that |R| vertices of G are red and |B| vertices of G are blue. A bichromatic point-set embedding of G on R ∪ B is a crossing-free drawing of G such that each blue vertex is mapped to a point of B, each red vertex is mapped to a point of R, and each edge is a polygonal curve. We study the curve complexity of bichromatic point-set embeddings; i.e., the number of bends per edge that are necessary and sufficient to compute such drawings. We show that O(n) bends are sometimes necessary. We also prove that two bends per edge suffice if G is a 2-colored caterpillar and that for properly 2-colored caterpillars, properly 2-colored wreaths, 2-colored paths, and 2-colored cycles the number of bends per edge can be reduced to one, which is worst-case optimal.

Styles APA, Harvard, Vancouver, ISO, etc.

7

Mao, Yaping, Zhao Wang, Fengnan Yanling et Chengfu Ye. « Monochromatic connectivity and graph products ». Discrete Mathematics, Algorithms and Applications 08, n^o 01 (26 février 2016) : 1650011. http://dx.doi.org/10.1142/s1793830916500117.

Texte intégral

Résumé :

The concept of monochromatic connectivity was introduced by Caro and Yuster. A path in an edge-colored graph is called a monochromatic path if all the edges on the path are colored the same. An edge-coloring of [Formula: see text] is a monochromatic connection coloring ([Formula: see text]-coloring, for short) if there is a monochromatic path joining any two vertices in [Formula: see text]. The monochromatic connection number, denoted by [Formula: see text], is defined to be the maximum number of colors used in an [Formula: see text]-coloring of a graph [Formula: see text]. In this paper, we study the monochromatic connection number on the lexicographical, strong, Cartesian and direct products and present several upper and lower bounds for these products of graphs.

Styles APA, Harvard, Vancouver, ISO, etc.

8

Ma, Hongping, Zhengke Miao, Hong Zhu, Jianhua Zhang et Rong Luo. « Strong List Edge Coloring of Subcubic Graphs ». Mathematical Problems in Engineering 2013 (2013) : 1–6. http://dx.doi.org/10.1155/2013/316501.

Texte intégral

Résumé :

We study strong list edge coloring of subcubic graphs, and we prove that every subcubic graph with maximum average degree less than 15/7, 27/11, 13/5, and 36/13 can be strongly list edge colored with six, seven, eight, and nine colors, respectively.

Styles APA, Harvard, Vancouver, ISO, etc.

9

Hou, Rui, Ji-Gang Wu, Yawen Chen, Haibo Zhang et Xiu-Feng Sui. « Constructing Edge-Colored Graph for Heterogeneous Networks ». Journal of Computer Science and Technology 30, n^o 5 (septembre 2015) : 1154–60. http://dx.doi.org/10.1007/s11390-015-1551-0.

Texte intégral

Styles APA, Harvard, Vancouver, ISO, etc.

10

Simonyi, Gábor. « On Colorful Edge Triples in Edge-Colored Complete Graphs ». Graphs and Combinatorics 36, n^o 6 (9 septembre 2020) : 1623–37. http://dx.doi.org/10.1007/s00373-020-02214-4.

Texte intégral

Résumé :

Abstract An edge-coloring of the complete graph $$K_n$$ K n we call F-caring if it leaves no F-subgraph of $$K_n$$ K n monochromatic and at the same time every subset of |V(F)| vertices contains in it at least one completely multicolored version of F. For the first two meaningful cases, when $$F=K_{1,3}$$ F = K 1 , 3 and $$F=P_4$$ F = P 4 we determine for infinitely many n the minimum number of colors needed for an F-caring edge-coloring of $$K_n$$ K n . An explicit family of $$2\lceil \log _2 n\rceil $$ 2 ⌈ log 2 n ⌉ 3-edge-colorings of $$K_n$$ K n so that every quadruple of its vertices contains a totally multicolored $$P_4$$ P 4 in at least one of them is also presented. Investigating related Ramsey-type problems we also show that the Shannon (OR-)capacity of the Grötzsch graph is strictly larger than that of the cycle of length 5.

Styles APA, Harvard, Vancouver, ISO, etc.

11

Wang, Yiqiao, Juan Liu, Yongtang Shi et Weifan Wang. « Star Chromatic Index of 1-Planar Graphs ». Symmetry 14, n^o 6 (8 juin 2022) : 1177. http://dx.doi.org/10.3390/sym14061177.

Texte intégral

Résumé :

Many symmetric properties are well-explored in graph theory, especially in graph coloring, such as symmetric graphs defined by the automorphism groups, symmetric drawing of planar graphs, and symmetric functions which are used to count the number of specific colorings of a graph. This paper is devoted to studying the star edge coloring of 1-planar graphs. The star chromatic index χst′(G) of a graph G is defined as the smallest k for which the edges of G can be colored by using k colors so that no two adjacent edges get the same color and no bichromatic paths or cycles of length four are produced. A graph G is called 1-planar if it can be drawn in the plane such that each edge crosses at most one other edge. In this paper, we prove that every 1-planar graph G satisfies χst′(G)≤7.75Δ+166; and moreover χst′(G)≤⌊1.5Δ⌋+500 if G contains no 4-cycles, and χst′(G)≤2.75Δ+116 if G is 3-connected, or optimal, or NIC-planar.

Styles APA, Harvard, Vancouver, ISO, etc.

12

Xiang, Changyuan, Yongxin Lan, Qinghua Yan et Changqing Xu. « The Outer-Planar Anti-Ramsey Number of Matchings ». Symmetry 14, n^o 6 (16 juin 2022) : 1252. http://dx.doi.org/10.3390/sym14061252.

Texte intégral

Résumé :

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.

Styles APA, Harvard, Vancouver, ISO, etc.

13

Marhelina, Sally. « RAINBOW CONNECTION PADA GRAF k -CONNECTED UNTUK k = 1 ATAU 2 ». Jurnal Matematika UNAND 2, n^o 1 (10 mars 2013) : 78. http://dx.doi.org/10.25077/jmu.2.1.78-84.2013.

Texte intégral

Résumé :

An edge-colored graph G is rainbow connected if any two vertices are connected by a path whose edges have distinct colors. The rainbow connection number of aconnected graph G, denoted by rc(G) is the smallest number of colors needed such thatG is rainbow connected. In this paper, we will proved again that rc(G) ≤ 3(n + 1)/5 forall 3-connected graphs, and rc(G) ≤ 2n/3 for all 2-connected graphs.

Styles APA, Harvard, Vancouver, ISO, etc.

14

Gorbenko, Anna. « Graph-Theoretic Models for the Module of Safe Planning for Control Systems of Mobile Robots ». Advanced Materials Research 683 (avril 2013) : 737–40. http://dx.doi.org/10.4028/www.scientific.net/amr.683.737.

Texte intégral

Résumé :

In this paper, we propose an approach to the creation of safe planning module for control systems of mobile robots. Our approach is based on some graph-theoretic models. In particular, we consider models of monochromatic and alternating paths for edge-colored graphs.

Styles APA, Harvard, Vancouver, ISO, etc.

15

Awanis, Zata Yumni, et A. N. M. Salman. « The strong 3-rainbow index of some certain graphs and its amalgamation ». Opuscula Mathematica 42, n^o 4 (2022) : 527–47. http://dx.doi.org/10.7494/opmath.2022.42.4.527.

Texte intégral

Résumé :

We introduce a strong $k$-rainbow index of graphs as modification of well-known $k$-rainbow index of graphs. A tree in an edge-colored connected graph $G$, where adjacent edge may be colored the same, is a rainbow tree if all of its edges have distinct colors. Let $k$ be an integer with $2\leq k\leq n$. The strong $k$-rainbow index of $G$, denoted by $srx_k(G)$, is the minimum number of colors needed in an edge-coloring of $G$ so that every $k$ vertices of $G$ is connected by a rainbow tree with minimum size. We focus on $k=3$. We determine the strong $3$-rainbow index of some certain graphs. We also provide a sharp upper bound for the strong $3$-rainbow index of amalgamation of graphs. Additionally, we determine the exact values of the strong $3$-rainbow index of amalgamation of some graphs.

Styles APA, Harvard, Vancouver, ISO, etc.

16

Yin, Huixin, Miaomiao Han et Murong Xu. « Strong Edge Coloring of K4(t)-Minor Free Graphs ». Axioms 12, n^o 6 (5 juin 2023) : 556. http://dx.doi.org/10.3390/axioms12060556.

Texte intégral

Résumé :

A strong edge coloring of a graph G is a proper coloring of edges in G such that any two edges of distance at most 2 are colored with distinct colors. The strong chromatic index χs′(G) is the smallest integer l such that G admits a strong edge coloring using l colors. A K4(t)-minor free graph is a graph that does not contain K4(t) as a contraction subgraph, where K4(t) is obtained from a K4 by subdividing edges exactly t−4 times. The paper shows that every K4(t)-minor free graph with maximum degree Δ(G) has χs′(G)≤(t−1)Δ(G) for t∈{5,6,7} which generalizes some known results on K4-minor free graphs by Batenburg, Joannis de Verclos, Kang, Pirot in 2022 and Wang, Wang, and Wang in 2018. These upper bounds are sharp.

Styles APA, Harvard, Vancouver, ISO, etc.

17

Jin, Zemin, Huawei Ma et Rui Yu. « Rainbow matchings in an edge-colored planar bipartite graph ». Applied Mathematics and Computation 432 (novembre 2022) : 127356. http://dx.doi.org/10.1016/j.amc.2022.127356.

Texte intégral

Styles APA, Harvard, Vancouver, ISO, etc.

18

Erzurumluoğlu, Aras, et C. A. Rodger. « On Evenly-Equitable, Balanced Edge-Colorings and Related Notions ». International Journal of Combinatorics 2015 (4 mars 2015) : 1–7. http://dx.doi.org/10.1155/2015/201427.

Texte intégral

Résumé :

A graph G is said to be even if all vertices of G have even degree. Given a k-edge-coloring of a graph G, for each color i∈Zk={0,1,…,k-1} let G(i) denote the spanning subgraph of G in which the edge-set contains precisely the edges colored i. A k-edge-coloring of G is said to be an even k-edge-coloring if for each color i∈Zk, G(i) is an even graph. A k-edge-coloring of G is said to be evenly-equitable if for each color i∈Zk, G(i) is an even graph, and for each vertex v∈V(G) and for any pair of colors i,j∈Zk, |degG(i)(v)-degG(j)(v)|∈{0,2}. For any pair of vertices {v,w} let mG({v,w}) be the number of edges between v and w in G (we allow v=w, where {v,v} denotes a loop incident with v). A k-edge-coloring of G is said to be balanced if for all pairs of colors i and j and all pairs of vertices v and w (possibly v=w), |mG(i)({v,w})-mG(j)({v,w})|≤1. Hilton proved that each even graph has an evenly-equitable k-edge-coloring for each k∈N. In this paper we extend this result by finding a characterization for graphs that have an evenly-equitable, balanced k-edge-coloring for each k∈N. Correspondingly we find a characterization for even graphs to have an evenly-equitable, balanced 2-edge-coloring. Then we give an instance of how evenly-equitable, balanced edge-colorings can be used to determine if a certain fairness property of factorizations of some regular graphs is satisfied. Finally we indicate how different fairness notions on edge-colorings interact with each other.

Styles APA, Harvard, Vancouver, ISO, etc.

19

Chen, Ming, Lianying Miao et Shan Zhou. « Strong Edge Coloring of Generalized Petersen Graphs ». Mathematics 8, n^o 8 (2 août 2020) : 1265. http://dx.doi.org/10.3390/math8081265.

Texte intégral

Résumé :

A strong edge coloring of a graph G is a proper edge coloring such that every color class is an induced matching. In 2018, Yang and Wu proposed a conjecture that every generalized Petersen graph P(n,k) with k≥4 and n>2k can be strong edge colored with (at most) seven colors. Although the generalized Petersen graph P(n,k) is a kind of special graph, the strong chromatic index of P(n,k) is still unknown. In this paper, we support the conjecture by showing that the strong chromatic index of every generalized Petersen graph P(n,k) with k≥4 and n>2k is at most 9.

Styles APA, Harvard, Vancouver, ISO, etc.

20

Adawiyah, Robiatul, Indi Izzah Makhfudloh et Rafiantika Megahnia Prihandini. « Local edge (a, d) –antimagic coloring on sunflower, umbrella graph and its application ». Alifmatika : Jurnal Pendidikan dan Pembelajaran Matematika 5, n^o 1 (15 juin 2023) : 70–81. http://dx.doi.org/10.35316/alifmatika.2023.v5i1.70-81.

Texte intégral

Résumé :

Suppose a graph G = (V, E) is a simple, connected and finite graph with vertex set V(G) and an edge set E(G). The local edge antimagic coloring is a combination of local antimagic labelling and edge coloring. A mapping f∶ V (G)→ {1, 2, ..., |V (G)|} is called local edge antimagic coloring if every two incident edges e_1and e_2, then the edge weights of e_1and e_2 maynot be the same, w(e_1) ≠ w(e_2), with e = uv ∈ G, w(e) = f(u)+ f(v) with the rule that the edges e are colored according to their weights, w_e. Local edge antimagic coloring has developed into local (a,d)-antimagic coloring. Local antimagic coloring is called local (a,d)-antimagic coloring if the set of edge weights forms an arithmetic sequence with a as an initial value and d as a difference value. The graphs used in this study are sunflower graphs and umbrella graphs. This research will also discuss one of the applications of local edge (a,d)-antimagic coloring, namely the design of the Sidoarjo line batik motif. The result show that χ_le(3,1) (Sf_n) = 3n and χ_le(3n/2,1) (U_(m,n) ) = m+1 . The local (a,d)-antimagic coloring is formed into a batik motif design with characteristics from the Sidoarjo region.

Styles APA, Harvard, Vancouver, ISO, etc.

21

SUN, YUEFANG. « The (3, l)-Rainbow Edge-Index of Cartesian Product Graphs ». Journal of Interconnection Networks 17, n^o 03n04 (septembre 2017) : 1741009. http://dx.doi.org/10.1142/s0219265917410092.

Texte intégral

Résumé :

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.

Styles APA, Harvard, Vancouver, ISO, etc.

22

Kellerhals, Leon, Tomohiro Koana, Pascal Kunz et Rolf Niedermeier. « Parameterized Algorithms for Colored Clustering ». Proceedings of the AAAI Conference on Artificial Intelligence 37, n^o 4 (26 juin 2023) : 4400–4408. http://dx.doi.org/10.1609/aaai.v37i4.25560.

Texte intégral

Résumé :

In the Colored Clustering problem, one is asked to cluster edge-colored (hyper-)graphs whose colors represent interaction types. More specifically, the goal is to select as many edges as possible without choosing two edges that share an endpoint and are colored differently. Equivalently, the goal can also be described as assigning colors to the vertices in a way that fits the edge-coloring as well as possible. As this problem is NP-hard, we build on previous work by studying its parameterized complexity. We give a 2ᴼ⁽ᵏ⁾·nᴼ⁽¹⁾-time algorithm where k is the number of edges to be selected and n the number of vertices. We also prove the existence of a problem kernel of size O(k⁵ᐟ²), resolving an open problem posed in the literature. We consider parameters that are smaller than k, the number of edges to be selected, and r, the number of edges that can be deleted. Such smaller parameters are obtained by considering the difference between k or r and some lower bound on these values. We give both algorithms and lower bounds for Colored Clustering with such parameterizations. Finally, we settle the parameterized complexity of Colored Clustering with respect to structural graph parameters by showing that it is W[1]-hard with respect to both vertex cover number and tree-cut width, but fixed-parameter tractable with respect to local feedback edge number.

Styles APA, Harvard, Vancouver, ISO, etc.

23

Levin, M. Sh. « On models of clustering based on edge colored in graph ». Information Processes 22, n^o 2 (2022) : 119–28. http://dx.doi.org/10.53921/18195822_2022_22_2_119.

Texte intégral

Styles APA, Harvard, Vancouver, ISO, etc.

24

Adawiyah, R., I. I. Makhfudloh, Dafik Dafik, RM Prihandini et AC Prihandoko. « ON RAINBOW ANTIMAGIC COLORING OF SNAIL GRAPH(S_n ), COCONUT ROOT GRAPH (Cr_(n,m) ), FAN STALK GRAPH (Kt_n ) AND THE LOTUS GRAPH(Lo_n ) ». BAREKENG : Jurnal Ilmu Matematika dan Terapan 17, n^o 3 (30 septembre 2023) : 1543–52. http://dx.doi.org/10.30598/barekengvol17iss3pp1543-1552.

Texte intégral

Résumé :

Rainbow antimagic coloring is a combination of antimagic labeling and rainbow coloring. Antimagic labeling is labeling of each vertex of the graph with a different label, so that each the sum of the vertices in the graph has a different weight. Rainbow coloring is part of the rainbow-connected edge coloring, where each graph has a rainbow path. A rainbow path in a graph is formed if two vertices on the graph do not have the same color. If the given color on each edge is different, for example in the function it is colored with a weight , it is called rainbow antimagic coloring. Rainbow antimagic coloring has a condition that every two vertices on a graph cannot have the same rainbow path. The minimum number of colors from rainbow antimagic coloring is called the rainbow antimagic connection number, denoted by In this study, we analyze the rainbow antimagic connection number of snail graph , coconut root graph , fan stalk graph and lotus graph .

Styles APA, Harvard, Vancouver, ISO, etc.

25

Kézdy, AndréE, et Chi Wang. « Alternating walks in partially 2-edge-colored graphs and optimal strength of graph labeling ». Discrete Mathematics 194, n^o 1-3 (janvier 1999) : 261–65. http://dx.doi.org/10.1016/s0012-365x(98)00148-4.

Texte intégral

Styles APA, Harvard, Vancouver, ISO, etc.

26

Salman, A. N. M., Z. Y. Awanis et S. W. Saputro. « Graphs with strong 3-rainbow index equals 2 ». Journal of Physics : Conference Series 2157, n^o 1 (1 janvier 2022) : 012011. http://dx.doi.org/10.1088/1742-6596/2157/1/012011.

Texte intégral

Résumé :

Abstract Let G be an edge-colored connected graph of order n ≥ 3, where adjacent edges may be colored the same. Let k be an integer with 2 ≤ k ≤ n and S ⊆ V (G) with |S| = k. The Steiner distance d(S) of S is the minimum size of a tree in G connecting S. The strong k-rainbow index srxk (G) of G is the minimum number of colors required to color the edges of G so that every set S in G is connected by a tree of size d(S) whose edges have distinct colors. We focus on k = 3. In this paper, we first characterize the graphs G with srx 3 (G) = 2. According to the definition, it is clearly that ‖G‖ is the trivial upper bound for srx 3(G). Several previous researchers have shown that there exist some connected graphs G such that srx 3(G) = ‖G‖. Hence, in this paper, we provide another graph G such that srx 3(G) = ‖G‖.

Styles APA, Harvard, Vancouver, ISO, etc.

27

Ensor, Andrew, et Felipe Lillo. « Colored-Edge Graph Approach for the Modeling of Multimodal Transportation Systems ». Asia-Pacific Journal of Operational Research 33, n^o 01 (février 2016) : 1650005. http://dx.doi.org/10.1142/s0217595916500056.

Texte intégral

Résumé :

Many networked systems involve multiple modes of transport. Such systems are called multimodal, and examples include logistic networks, biomedical phenomena and telecommunication networks. Existing techniques for determining minimal paths in multimodal networks have either required heuristics or else application-specific constraints to obtain tractable problems, removing the multimodal traits of the network during analysis. In this paper weighted colored-edge graphs are introduced for modeling multimodal networks, where colors represent the modes of transportation. Minimal paths are selected using a partial order that compares the weights in each color, resulting in a Pareto set of minimal paths. Although the computation of minimal paths is theoretically intractable and [Formula: see text]-complete, the approach is shown to be tractable through experimental analyses without the need to apply heuristics or constraints.

Styles APA, Harvard, Vancouver, ISO, etc.

28

Mertzios, George B., Hendrik Molter et Viktor Zamaraev. « Sliding Window Temporal Graph Coloring ». Proceedings of the AAAI Conference on Artificial Intelligence 33 (17 juillet 2019) : 7667–74. http://dx.doi.org/10.1609/aaai.v33i01.33017667.

Texte intégral

Résumé :

Graph coloring is one of the most famous computational problems with applications in a wide range of areas such as planning and scheduling, resource allocation, and pattern matching. So far coloring problems are mostly studied on static graphs, which often stand in stark contrast to practice where data is inherently dynamic and subject to discrete changes over time. A temporal graph is a graph whose edges are assigned a set of integer time labels, indicating at which discrete time steps the edge is active. In this paper we present a natural temporal extension of the classical graph coloring problem. Given a temporal graph and a natural number ∆, we ask for a coloring sequence for each vertex such that (i) in every sliding time window of ∆ consecutive time steps, in which an edge is active, this edge is properly colored (i.e. its endpoints are assigned two different colors) at least once during that time window, and (ii) the total number of different colors is minimized. This sliding window temporal coloring problem abstractly captures many realistic graph coloring scenarios in which the underlying network changes over time, such as dynamically assigning communication channels to moving agents. We present a thorough investigation of the computational complexity of this temporal coloring problem. More specifically, we prove strong computational hardness results, complemented by efficient exact and approximation algorithms. Some of our algorithms are linear-time fixed-parameter tractable with respect to appropriate parameters, while others are asymptotically almost optimal under the Exponential Time Hypothesis (ETH).

Styles APA, Harvard, Vancouver, ISO, etc.

29

Kristiana, Arika Indah, Ahmad Aji, Edy Wihardjo et Deddy Setiawan. « on Graceful Chromatic Number of Vertex amalgamation of Tree Graph Family ». CAUCHY : Jurnal Matematika Murni dan Aplikasi 7, n^o 3 (11 octobre 2022) : 432–44. http://dx.doi.org/10.18860/ca.v7i3.16334.

Texte intégral

Résumé :

Proper vertex coloring c of a graph G is a graceful coloring if c is a graceful k-coloring for k∈{1,2,3,…}. Definition graceful k-coloring of a graph G=(V,E) is a proper vertex coloring c:V(G)→{1,2,…,k);k≥2, which induces a proper edge coloring c':E(G)→{1,2,…,k-1} defined c'(uv)=|c(u)-c(v)|. The minimum vertex coloring from graph G can be colored with graceful coloring called a graceful chromatic number with notation χg (G). In this paper, we will investigate the graceful chromatic number of vertex amalgamation of tree graph family with some graph is path graph, centipede graph, broom and E graph.

Styles APA, Harvard, Vancouver, ISO, etc.

30

FU, JINGCHENG, GUANGHUI WANG, JIANLIANG WU et JIN XU. « A NOTE ON EDGE WEIGHT CHOOSABILITY OF GRAPHS ». Discrete Mathematics, Algorithms and Applications 06, n^o 01 (18 février 2014) : 1450010. http://dx.doi.org/10.1142/s1793830914500104.

Texte intégral

Résumé :

In 2004, Karoński, Łuczak, and Thomason conjectured that the edges of any connected graph on at least 3 vertices may be weighted from the set {1, 2, 3} so that the vertices are properly colored by the sums of their incident edge weights. Bartnicki, Grytczuk and Niwcyk introduced its list version. Assign to each edge e ∈ E(G) a list of k real numbers, say L(e), and choose a weight w(e) ∈ L(e) for each e ∈ E(G). The resulting function w : E(G) → ⋃e∈E(G) L(e) is called an edge k-list-weighting. Given a graph G, the smallest k such that any assignment of lists of size k to E(G) permits an edge k-list-weighting which is a vertex coloring by sums is denoted by [Formula: see text] and called the edge weight choosability of G. Bartnicki, Grytczuk and Niwcyk conjectured that if G is a nice graph (without a component isomorphic to K2), then [Formula: see text]. There is no known constant K such that [Formula: see text] for any nice graph G. Ben Seamone proved that [Formula: see text] for any nice graph G with maximum degree Δ(G) by using Alon's Combinatorial Nullstellensatz. In this paper, we improve this bound to [Formula: see text].

Styles APA, Harvard, Vancouver, ISO, etc.

31

Razumovsky, P. V. « The search for minimal edge 1-extension of an undirected colored graph ». Izvestia of Saratov University. New Series. Series : Mathematics. Mechanics. Informatics 21, n^o 3 (25 août 2021) : 400–407. http://dx.doi.org/10.18500/1816-9791-2021-21-3-400-407.

Texte intégral

Styles APA, Harvard, Vancouver, ISO, etc.

32

Botea, Adi, Massimiliano Mattetti, Akihiro Kishimoto, Radu Marinescu et Elizabeth Daly. « Counting Vertex-Disjoint Shortest Paths in Graphs ». Proceedings of the International Symposium on Combinatorial Search 12, n^o 1 (21 juillet 2021) : 28–36. http://dx.doi.org/10.1609/socs.v12i1.18548.

Texte intégral

Résumé :

Finding a shortest path in a graph is at the core of many combinatorial search problems. A closely related problem refers to counting the number of shortest paths between two nodes. Such problems are solvable in polynomial time in the size of the graph. However, more realistic problem formulations could additionally specify constraints to satisfy. We study the problem of counting the shortest paths that are vertex disjoint and can satisfy additional constraints. Specifically, we look at the problems of counting vertex-disjoint shortest paths in edge-colored graphs, counting vertex-disjoint shortest paths with directional constraints, and counting vertex-disjoint shortest paths between multiple source-target pairs. We give a detailed theoretical analysis, and show formally that all of these three counting problems are NP-complete in general.

Styles APA, Harvard, Vancouver, ISO, etc.

33

WANG, GUANGHUI, BINGQIANG LIU et GUIZHEN LIU. « A NOTE ON RAINBOW MATCHINGS ». Discrete Mathematics, Algorithms and Applications 05, n^o 04 (décembre 2013) : 1350028. http://dx.doi.org/10.1142/s1793830913500286.

Texte intégral

Résumé :

Let G be a d-regular properly edge-colored graph such that the edges with the same color induce a 1-factor of G. A rainbow matching of G is a matching in which no two edges have the same color. We show that if the order n of G is at least 3.79d, then G has a rainbow matching of size d.

Styles APA, Harvard, Vancouver, ISO, etc.

34

DINITZ, YEFIM, MATTHEW J. KATZ et ROI KRAKOVSKI. « GUARDING RECTANGULAR PARTITIONS ». International Journal of Computational Geometry & ; Applications 19, n^o 06 (décembre 2009) : 579–94. http://dx.doi.org/10.1142/s0218195909003131.

Texte intégral

Résumé :

A rectangular partition is a partition of a rectangle into non-overlapping rectangles, such that no four rectangles meet at a common point. A vertex guard is a guard located at a vertex of the partition (i.e., at a corner of a rectangle); it guards the rectangles that meet at this vertex. An edge guard is a guard that patrols along an edge of the partition, and is thus equivalent to two adjacent vertex guards. We consider the problem of finding a minimum-cardinality guarding set for the rectangles of the partition. For vertex guards, we prove that guarding a given subset of the rectangles is NP-hard. For edge guards, we prove that guarding all rectangles, where guards are restricted to a given subset of the edges, is NP-hard. For both results we show a reduction from vertex cover in non-bipartite 3-connected cubic planar graphs of girth greater than three. For the second NP-hardness result, we obtain a graph-theoretic result which establishes a connection between the set of faces of a plane graph of vertex degree at most three and a vertex cover for this graph. More precisely, we prove that one can assign to each internal face a distinct vertex of the cover, which lies on the face's boundary. We show that the vertices of a rectangular partition can be colored red, green, or black, such that each rectangle has all three colors on its boundary. We conjecture that the above is also true for four colors. Finally, we obtain a worst-case upper bound on the number of edge guards that are sufficient for guarding rectangular partitions with some restrictions on their structure.

Styles APA, Harvard, Vancouver, ISO, etc.

35

Jia, Mingshan, Maité Van Alboom, Liesbet Goubert, Piet Bracke, Bogdan Gabrys et Katarzyna Musial. « Encoding edge type information in graphlets ». PLOS ONE 17, n^o 8 (26 août 2022) : e0273609. http://dx.doi.org/10.1371/journal.pone.0273609.

Texte intégral

Résumé :

Graph embedding approaches have been attracting increasing attention in recent years mainly due to their universal applicability. They convert network data into a vector space in which the graph structural information and properties are maximumly preserved. Most existing approaches, however, ignore the rich information about interactions between nodes, i.e., edge attribute or edge type. Moreover, the learned embeddings suffer from a lack of explainability, and cannot be used to study the effects of typed structures in edge-attributed networks. In this paper, we introduce a framework to embed edge type information in graphlets and generate a Typed-Edge Graphlets Degree Vector (TyE-GDV). Additionally, we extend two combinatorial approaches, i.e., the colored graphlets and heterogeneous graphlets approaches to edge-attributed networks. Through applying the proposed method to a case study of chronic pain patients, we find that not only the network structure of a patient could indicate his/her perceived pain grade, but also certain social ties, such as those with friends, colleagues, and healthcare professionals, are more crucial in understanding the impact of chronic pain. Further, we demonstrate that in a node classification task, the edge-type encoded graphlets approaches outperform the traditional graphlet degree vector approach by a significant margin, and that TyE-GDV could achieve a competitive performance of the combinatorial approaches while being far more efficient in space requirements.

Styles APA, Harvard, Vancouver, ISO, etc.

36

Zhang, Yixin, Yanbo Zhang et Hexuan Zhi. « A proof of a conjecture on matching-path connected size Ramsey number ». AIMS Mathematics 8, n^o 4 (2023) : 8027–33. http://dx.doi.org/10.3934/math.2023406.

Texte intégral

Résumé :

<abstract><p>For two graphs $ G_1 $ and $ G_2 $, the connected size Ramsey number $ {\hat{r}}_c(G_1, G_2) $ is the smallest number of edges of a connected graph $ G $ such that if each edge of $ G $ is colored red or blue, then $ G $ contains either a red copy of $ G_1 $ or a blue copy of $ G_2 $. Let $ nK_2 $ be a matching with $ n $ edges and $ P_4 $ a path with four vertices. Rahadjeng, Baskoro, and Assiyatun [Procedia Comput. Sci. 74 (2015), 32-37] conjectured that $ \hat{r}_{c}(nK_2, P_4) = 3n-1 $ if $ n $ is even, and $ \hat{r}_{c}(nK_2, P_4) = 3n $ otherwise. We verify the conjecture in this short paper.</p></abstract>

Styles APA, Harvard, Vancouver, ISO, etc.

37

Zhao, Peixue, et Fei Huang. « Rainbow vertex pair-pancyclicity of strongly edge-colored graphs ». Discrete Mathematics & ; Theoretical Computer Science 25:1, Graph Theory (16 mai 2023). http://dx.doi.org/10.46298/dmtcs.10142.

Texte intégral

Résumé :

An edge-colored graph is \emph{rainbow }if no two edges of the graph have the same color. An edge-colored graph $G^c$ is called \emph{properly colored} if every two adjacent edges of $G^c$ receive distinct colors in $G^c$. A \emph{strongly edge-colored} graph is a proper edge-colored graph such that every path of length $3$ is rainbow. We call an edge-colored graph $G^c$ \emph{rainbow vertex pair-pancyclic} if any two vertices in $G^c$ are contained in a rainbow cycle of length $\ell$ for each $\ell$ with $3 \leq \ell \leq n$. In this paper, we show that every strongly edge-colored graph $G^c$ of order $n$ with minimum degree $\delta \geq \frac{2n}{3}+1$ is rainbow vertex pair-pancyclicity.

Styles APA, Harvard, Vancouver, ISO, etc.

38

Bai, Shuliang, et Linyuan Lu. « Turán Density of $2$-Edge-Colored Bipartite Graphs with Application on $\{2, 3\}$-Hypergraphs ». Electronic Journal of Combinatorics 28, n^o 3 (27 août 2021). http://dx.doi.org/10.37236/10068.

Texte intégral

Résumé :

We consider the Turán problems of $2$-edge-colored graphs. A $2$-edge-colored graph $H=(V, E_r, E_b)$ is a triple consisting of the vertex set $V$, the set of red edges $E_r$ and the set of blue edges $E_b$ where $E_r$ and $E_b$ do not have to be disjoint. The Turán density $\pi(H)$ of $H$ is defined to be $\lim_{n\to\infty} \max_{G_n}h_n(G_n)$, where $G_n$ is chosen among all possible $2$-edge-colored graphs on $n$ vertices containing no $H$ as a sub-graph and $h_n(G_n)=(|E_r(G)|+|E_b(G)|)/\binom{n}{2}$ is the formula to measure the edge density of $G_n$. We will determine the Turán densities of all $2$-edge-colored bipartite graphs. We also give an important application on the Turán problems of $\{2, 3\}$-hypergraphs.

Styles APA, Harvard, Vancouver, ISO, etc.

39

Fujita, Shinya, Michitaka Furuya, András Gyárfás et Ágnes Tóth. « Partition of Graphs and Hypergraphs into Monochromatic Connected Parts ». Electronic Journal of Combinatorics 19, n^o 3 (30 août 2012). http://dx.doi.org/10.37236/2121.

Texte intégral

Résumé :

We show that two results on covering of edge colored graphs by monochromatic connected parts can be extended to partitioning. We prove that for any $2$-edge-colored non-trivial $r$-uniform hypergraph $H$, the vertex set can be partitioned into at most $\alpha (H)-r+2$ monochromatic connected parts, where $\alpha (H)$ is the maximum number of vertices that does not contain any edge. In particular, any $2$-edge-colored graph $G$ can be partitioned into $\alpha(G)$ monochromatic connected parts, where $\alpha (G)$ denotes the independence number of $G$. This extends König's theorem, a special case of Ryser's conjecture. Our second result is about Gallai-colorings, i.e. edge-colorings of graphs without $3$-edge-colored triangles. We show that for any Gallai-coloring of a graph $G$, the vertex set of $G$ can be partitioned into monochromatic connected parts, where the number of parts depends only on $\alpha(G)$. This extends its cover-version proved earlier by Simonyi and two of the authors.

Styles APA, Harvard, Vancouver, ISO, etc.

40

Eckstein, Nils Jakob, Niels Grüttemeier, Christian Komusiewicz et Frank Sommer. « Destroying Multicolored Paths and Cycles in Edge-Colored Graphs ». Discrete Mathematics & ; Theoretical Computer Science 25:1, Graph Theory (3 mars 2023). http://dx.doi.org/10.46298/dmtcs.7636.

Texte intégral

Résumé :

We study the computational complexity of $c$-Colored $P_\ell$ Deletion and $c$-Colored $C_\ell$ Deletion. In these problems, one is given a $c$-edge-colored graph and wants to destroy all induced $c$-colored paths or cycles, respectively, on $\ell$ vertices by deleting at most $k$ edges. Herein, a path or cycle is $c$-colored if it contains edges of $c$ distinct colors. We show that $c$-Colored $P_\ell$ Deletion and $c$-Colored $C_\ell$ Deletion are NP-hard for each non-trivial combination of $c$ and $\ell$. We then analyze the parameterized complexity of these problems. We extend the notion of neighborhood diversity to edge-colored graphs and show that both problems are fixed-parameter tractable with respect to the colored neighborhood diversity of the input graph. We also provide hardness results to outline the limits of parameterization by the standard parameter solution size $k$. Finally, we consider bicolored input graphs and show a special case of $2$-Colored $P_4$ Deletion that can be solved in polynomial time.

Styles APA, Harvard, Vancouver, ISO, etc.

41

Guo, Zhiwei, Christoph Brause, Maximilian Geißer et Ingo Schiermeyer. « Compatible Spanning Circuits and Forbidden Induced Subgraphs ». Graphs and Combinatorics 40, n^o 1 (19 janvier 2024). http://dx.doi.org/10.1007/s00373-023-02735-8.

Texte intégral

Résumé :

AbstractA compatible spanning circuit in an edge-colored graph G (not necessarily properly) is defined as a closed trail containing all vertices of G in which any two consecutively traversed edges have distinct colors. The existence of extremal compatible spanning circuits (i.e., compatible Hamilton cycles and compatible Euler tours) has been studied extensively. Recently, sufficient conditions for the existence of compatible spanning circuits visiting each vertex at least a specified number of times in specific edge-colored graphs satisfying certain degree conditions have been established. In this paper, we continue the research on sufficient conditions for the existence of such compatible s-panning circuits. We consider edge-colored graphs containing no certain forbidden induced subgraphs. As applications, we also consider the existence of such compatible spanning circuits in edge-colored graphs G with κ(G) ≥ α(G), κ(G) ≥ α(G) − 1 and κ (G) ≥ α(G), respectively. In this context, κ(G), α(G) and κ (G) denote the connectivity, the independence number and the edge connectivity of a graph G, respectively.

Styles APA, Harvard, Vancouver, ISO, etc.

42

Fekete, Panna Tímea, Roland Molontay, Balázs Ráth et Kitti Varga. « Color-avoiding percolation and branching processes ». Journal of Applied Probability, 8 mars 2024, 1–25. http://dx.doi.org/10.1017/jpr.2023.115.

Texte intégral

Résumé :

Abstract We study a variant of the color-avoiding percolation model introduced by Krause et al., namely we investigate the color-avoiding bond percolation setup on (not necessarily properly) edge-colored Erdős–Rényi random graphs. We say that two vertices are color-avoiding connected in an edge-colored graph if, after the removal of the edges of any color, they are in the same component in the remaining graph. The color-avoiding connected components of an edge-colored graph are maximal sets of vertices such that any two of them are color-avoiding connected. We consider the fraction of vertices contained in color-avoiding connected components of a given size, as well as the fraction of vertices contained in the giant color-avoidin g connected component. It is known that these quantities converge, and the limits can be expressed in terms of probabilities associated to edge-colored branching process trees. We provide explicit formulas for the limit of the fraction of vertices contained in the giant color-avoiding connected component, and we give a simpler asymptotic expression for it in the barely supercritical regime. In addition, in the two-colored case we also provide explicit formulas for the limit of the fraction of vertices contained in color-avoiding connected components of a given size.

Styles APA, Harvard, Vancouver, ISO, etc.

43

Chen, He, et Xueliang Li. « Long Heterochromatic Paths in Edge-Colored Graphs ». Electronic Journal of Combinatorics 12, n^o 1 (29 juillet 2005). http://dx.doi.org/10.37236/1930.

Texte intégral

Résumé :

Let $G$ be an edge-colored graph. A heterochromatic path of $G$ is such a path in which no two edges have the same color. $d^c(v)$ denotes the color degree of a vertex $v$ of $G$. In a previous paper, we showed that if $d^c(v)\geq k$ for every vertex $v$ of $G$, then $G$ has a heterochromatic path of length at least $\lceil{k+1\over 2}\rceil$. It is easy to see that if $k=1,2$, $G$ has a heterochromatic path of length at least $k$. Saito conjectured that under the color degree condition $G$ has a heterochromatic path of length at least $\lceil{2k+1\over 3}\rceil$. Even if this is true, no one knows if it is a best possible lower bound. Although we cannot prove Saito's conjecture, we can show in this paper that if $3\leq k\leq 7$, $G$ has a heterochromatic path of length at least $k-1,$ and if $k\geq 8$, $G$ has a heterochromatic path of length at least $\lceil{3k\over 5}\rceil+1$. Actually, we can show that for $1\leq k\leq 5$ any graph $G$ under the color degree condition has a heterochromatic path of length at least $k$, with only one exceptional graph $K_4$ for $k=3$, one exceptional graph for $k=4$ and three exceptional graphs for $k=5$, for which $G$ has a heterochromatic path of length at least $k-1$. Our experience suggests us to conjecture that under the color degree condition $G$ has a heterochromatic path of length at least $k-1$.

Styles APA, Harvard, Vancouver, ISO, etc.

44

Bowen, Matt, Adriana Hansberg, Amanda Montejano et Alp Müyesser. « Colored Unavoidable Patterns and Balanceable Graphs ». Electronic Journal of Combinatorics 31, n^o 2 (3 mai 2024). http://dx.doi.org/10.37236/10571.

Texte intégral

Résumé :

We study a Turán-type problem on edge-colored complete graphs. We show that for any $r$ and $t$, any sufficiently large $r$-edge-colored complete graph on $n$ vertices with $\Omega(n^{2-1/tr^r})$ edges in each color contains a member from certain finite family $\mathcal{F}_t^r$ of $r$-edge-colored complete graphs. We conjecture that $\Omega(n^{2-1/t})$ edges in each color are sufficient to find a member from ${\mathcal{F}}_t^r$. A result of Girão and Narayanan confirms this conjecture when $r=2$. Next, we study a related problem where the corresponding Turán threshold is linear. We call an edge-coloring of a path $P_{rk}$ balanced if each color appears $k$ times in the coloring. We show that any $3$-edge-coloring of a large complete graph with $kn+o(n)$ edges in each color contains a balanced $P_{3k}$. This is tight up to a constant factor of $2$. For more colors, the problem becomes surprisingly more delicate. Already for $r=7$, we show that even $n^{2-o(1)}$ edges from each color does not guarantee existence of a balanced $P_{7k}$.

Styles APA, Harvard, Vancouver, ISO, etc.

45

Maezawa, Shun-ichi, et Akiko Yazawa. « Special Case of Rota's Basis Conjecture on Graphic Matroids ». Electronic Journal of Combinatorics 29, n^o 3 (23 septembre 2022). http://dx.doi.org/10.37236/10835.

Texte intégral

Résumé :

Gian-Carlo Rota conjectured that for any $n$ bases $B_1,B_2,\ldots,B_n$ in a matroid of rank $n$, there exist $n$ disjoint transversal bases of $B_1,B_2,\ldots,B_n$. The conjecture for graphic matroids corresponds to the problem of an edge-decomposition as follows; If an edge-colored connected multigraph $G$ has $n-1$ colors and the graph induced by the edges colored with $c$ is a spanning tree for each color $c$, then $G$ has $n-1$ mutually edge-disjoint rainbow spanning trees. In this paper, we prove that edge-colored graphs where the edges colored with $c$ induce a spanning star for each color $c$ can be decomposed into rainbow spanning trees.

Styles APA, Harvard, Vancouver, ISO, etc.

46

Galeana-Sánchez, Hortensia, Felipe Hernández-Lorenzana, Rocío Sánchez-López et Carlos Vilchis-Alfaro. « On the existence of cycles with restrictions in the color transitions in edge-colored complete graphs ». Boletín de la Sociedad Matemática Mexicana 30, n^o 2 (17 mai 2024). http://dx.doi.org/10.1007/s40590-024-00624-5.

Texte intégral

Résumé :

AbstractConsider the following edge-coloring of a graph G. Let H be a graph possibly with loops, an H-coloring of a graph G is defined as a function $$c : E(G) \rightarrow V(H).$$ c : E ( G ) → V ( H ) . We will say that G is an H-colored graph whenever we are taking a fixed H-coloring of G. A cycle $$(x_0,x_1,\ldots ,x_n,x_0),$$ ( x 0 , x 1 , … , x n , x 0 ) , in an H-colored graph, is an H-cycle if and only if $$(c(x_0x_1),c(x_1x_2),\ldots , c(x_nx_0),$$ ( c ( x 0 x 1 ) , c ( x 1 x 2 ) , … , c ( x n x 0 ) , $$c(x_0x_1))$$ c ( x 0 x 1 ) ) is a walk in H. Notice that the graph H determines what color transitions are allowed in a cycle in order to be an H-cycle, in particular, when H is a complete graph without loops, every H-cycle is a properly colored cycle. In this paper, we give conditions on an H-colored complete graph G, with local restrictions, implying that every vertex of G is contained in an H-cycle of length at least 5. As a consequence, we obtain a previous result about properly colored cycles. Finally, we show an infinite family of H-colored complete graphs fulfilling the conditions of the main theorem, where the graph H is not a complete k-partite graph for any k in $${\mathbb {N}}.$$ N .

Styles APA, Harvard, Vancouver, ISO, etc.

47

Fujita, Shinya, Atsushi Kaneko, Ingo Schiermeyer et Kazuhiro Suzuki. « A Rainbow $k$-Matching in the Complete Graph with $r$ Colors ». Electronic Journal of Combinatorics 16, n^o 1 (30 avril 2009). http://dx.doi.org/10.37236/140.

Texte intégral

Résumé :

An $r$-edge-coloring of a graph is an assignment of $r$ colors to the edges of the graph. An exactly $r$-edge-coloring of a graph is an $r$-edge-coloring of the graph that uses all $r$ colors. A matching of an edge-colored graph is called rainbow matching, if no two edges have the same color in the matching. In this paper, we prove that an exactly $r$-edge-colored complete graph of order $n$ has a rainbow matching of size $k(\ge 2)$ if $r \ge max\{{2k-3\choose 2}+2, {k-2\choose 2}+(k-2)(n-k+2)+2 \}$, $k \ge 2$, and $n \ge 2k+1$. The bound on $r$ is best possible.

Styles APA, Harvard, Vancouver, ISO, etc.

48

Schaller, David, Manuel Lafond, Peter F. Stadler, Nicolas Wieseke et Marc Hellmuth. « Indirect identification of horizontal gene transfer ». Journal of Mathematical Biology 83, n^o 1 (juillet 2021). http://dx.doi.org/10.1007/s00285-021-01631-0.

Texte intégral

Résumé :

AbstractSeveral implicit methods to infer horizontal gene transfer (HGT) focus on pairs of genes that have diverged only after the divergence of the two species in which the genes reside. This situation defines the edge set of a graph, the later-divergence-time (LDT) graph, whose vertices correspond to genes colored by their species. We investigate these graphs in the setting of relaxed scenarios, i.e., evolutionary scenarios that encompass all commonly used variants of duplication-transfer-loss scenarios in the literature. We characterize LDT graphs as a subclass of properly vertex-colored cographs, and provide a polynomial-time recognition algorithm as well as an algorithm to construct a relaxed scenario that explains a given LDT. An edge in an LDT graph implies that the two corresponding genes are separated by at least one HGT event. The converse is not true, however. We show that the complete xenology relation is described by an rs-Fitch graph, i.e., a complete multipartite graph satisfying constraints on the vertex coloring. This class of vertex-colored graphs is also recognizable in polynomial time. We finally address the question “how much information about all HGT events is contained in LDT graphs” with the help of simulations of evolutionary scenarios with a wide range of duplication, loss, and HGT events. In particular, we show that a simple greedy graph editing scheme can be used to efficiently detect HGT events that are implicitly contained in LDT graphs.

Styles APA, Harvard, Vancouver, ISO, etc.

49

Diemunsch, Jennifer, Michael Ferrara, Allan Lo, Casey Moffatt, Florian Pfender et Paul S. Wenger. « Rainbow Matchings of Size $\delta(G)$ in Properly Edge-Colored Graphs ». Electronic Journal of Combinatorics 19, n^o 2 (28 juin 2012). http://dx.doi.org/10.37236/2443.

Texte intégral

Résumé :

A rainbow matching in an edge-colored graph is a matching in which all the edges have distinct colors. Wang asked if there is a function $f(\delta)$ such that a properly edge-colored graph $G$ with minimum degree $\delta$ and order at least $f(\delta)$ must have a rainbow matching of size $\delta$. We answer this question in the affirmative; an extremal approach yields that $f(\delta) = 98\delta/23< 4.27\delta$ suffices. Furthermore, we give an $O(\delta(G)|V(G)|^2)$-time algorithm that generates such a matching in a properly edge-colored graph of order at least $6.5\delta$.

Styles APA, Harvard, Vancouver, ISO, etc.

50

Kritschgau, Jürgen. « Rainbow Matchings of size $m$ in Graphs with Total Color Degree at least $2mn$ ». Electronic Journal of Combinatorics 27, n^o 3 (24 juillet 2020). http://dx.doi.org/10.37236/8239.

Texte intégral

Résumé :

The existence of a rainbow matching given a minimum color degree, proper coloring, or triangle-free host graph has been studied extensively. This paper generalizes these problems to edge colored graphs with given total color degree. In particular, we find that if a graph $G$ has total color degree $2mn$ and satisfies some other properties, then $G$ contains a matching of size $m$. These other properties include $G$ being triangle-free, $C_4$-free, properly colored, or large enough.

Styles APA, Harvard, Vancouver, ISO, etc.

Articles de revues sur le sujet « Edge-colored graph »

Créez une référence correcte selon les styles APA, MLA, Chicago, Harvard et plusieurs autres