Journal articles: 'Edge-colored graph'

1

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

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

2

Arora, Ajay, Eddie Cheng, and Colton Magnant. "Proper Coloring Distance in Edge-Colored Cartesian Products of Complete Graphs and Cycles." Parallel Processing Letters 29, no. 04 (December 2019): 1950016. http://dx.doi.org/10.1142/s0129626419500166.

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

3

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

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

4

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

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

5

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

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

6

DI GIACOMO, EMILIO, GIUSEPPE LIOTTA, and FRANCESCO TROTTA. "ON EMBEDDING A GRAPH ON TWO SETS OF POINTS." International Journal of Foundations of Computer Science 17, no. 05 (October 2006): 1071–94. http://dx.doi.org/10.1142/s0129054106004273.

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

7

Mao, Yaping, Zhao Wang, Fengnan Yanling, and Chengfu Ye. "Monochromatic connectivity and graph products." Discrete Mathematics, Algorithms and Applications 08, no. 01 (February 26, 2016): 1650011. http://dx.doi.org/10.1142/s1793830916500117.

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

8

Ma, Hongping, Zhengke Miao, Hong Zhu, Jianhua Zhang, and 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.

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

9

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

Full text

APA, Harvard, Vancouver, ISO, and other styles

10

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

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

11

Wang, Yiqiao, Juan Liu, Yongtang Shi, and Weifan Wang. "Star Chromatic Index of 1-Planar Graphs." Symmetry 14, no. 6 (June 8, 2022): 1177. http://dx.doi.org/10.3390/sym14061177.

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

12

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.

Full text

Abstract:

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, and other styles

13

Marhelina, Sally. "RAINBOW CONNECTION PADA GRAF k -CONNECTED UNTUK k = 1 ATAU 2." Jurnal Matematika UNAND 2, no. 1 (March 10, 2013): 78. http://dx.doi.org/10.25077/jmu.2.1.78-84.2013.

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

14

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

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

15

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

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

16

Yin, Huixin, Miaomiao Han, and Murong Xu. "Strong Edge Coloring of K4(t)-Minor Free Graphs." Axioms 12, no. 6 (June 5, 2023): 556. http://dx.doi.org/10.3390/axioms12060556.

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

17

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

Full text

APA, Harvard, Vancouver, ISO, and other styles

18

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

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

19

Chen, Ming, Lianying Miao, and Shan Zhou. "Strong Edge Coloring of Generalized Petersen Graphs." Mathematics 8, no. 8 (August 2, 2020): 1265. http://dx.doi.org/10.3390/math8081265.

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

20

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

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

21

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.

Full text

Abstract:

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, and other styles

22

Kellerhals, Leon, Tomohiro Koana, Pascal Kunz, and Rolf Niedermeier. "Parameterized Algorithms for Colored Clustering." Proceedings of the AAAI Conference on Artificial Intelligence 37, no. 4 (June 26, 2023): 4400–4408. http://dx.doi.org/10.1609/aaai.v37i4.25560.

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

23

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

Full text

APA, Harvard, Vancouver, ISO, and other styles

24

Adawiyah, R., I. I. Makhfudloh, Dafik Dafik, RM Prihandini, and 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, no. 3 (September 30, 2023): 1543–52. http://dx.doi.org/10.30598/barekengvol17iss3pp1543-1552.

Full text

Abstract:

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 .

APA, Harvard, Vancouver, ISO, and other styles

25

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

Full text

APA, Harvard, Vancouver, ISO, and other styles

26

Salman, A. N. M., Z. Y. Awanis, and S. W. Saputro. "Graphs with strong 3-rainbow index equals 2." Journal of Physics: Conference Series 2157, no. 1 (January 1, 2022): 012011. http://dx.doi.org/10.1088/1742-6596/2157/1/012011.

Full text

Abstract:

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‖.

APA, Harvard, Vancouver, ISO, and other styles

27

Ensor, Andrew, and Felipe Lillo. "Colored-Edge Graph Approach for the Modeling of Multimodal Transportation Systems." Asia-Pacific Journal of Operational Research 33, no. 01 (February 2016): 1650005. http://dx.doi.org/10.1142/s0217595916500056.

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

28

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

Full text

Abstract:

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).

APA, Harvard, Vancouver, ISO, and other styles

29

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

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

30

FU, JINGCHENG, GUANGHUI WANG, JIANLIANG WU, and JIN XU. "A NOTE ON EDGE WEIGHT CHOOSABILITY OF GRAPHS." Discrete Mathematics, Algorithms and Applications 06, no. 01 (February 18, 2014): 1450010. http://dx.doi.org/10.1142/s1793830914500104.

Full text

Abstract:

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].

APA, Harvard, Vancouver, ISO, and other styles

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, no. 3 (August 25, 2021): 400–407. http://dx.doi.org/10.18500/1816-9791-2021-21-3-400-407.

Full text

APA, Harvard, Vancouver, ISO, and other styles

32

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

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

33

WANG, GUANGHUI, BINGQIANG LIU, and GUIZHEN LIU. "A NOTE ON RAINBOW MATCHINGS." Discrete Mathematics, Algorithms and Applications 05, no. 04 (December 2013): 1350028. http://dx.doi.org/10.1142/s1793830913500286.

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

34

DINITZ, YEFIM, MATTHEW J. KATZ, and ROI KRAKOVSKI. "GUARDING RECTANGULAR PARTITIONS." International Journal of Computational Geometry & Applications 19, no. 06 (December 2009): 579–94. http://dx.doi.org/10.1142/s0218195909003131.

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

35

Jia, Mingshan, Maité Van Alboom, Liesbet Goubert, Piet Bracke, Bogdan Gabrys, and Katarzyna Musial. "Encoding edge type information in graphlets." PLOS ONE 17, no. 8 (August 26, 2022): e0273609. http://dx.doi.org/10.1371/journal.pone.0273609.

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

36

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

Full text

Abstract:

<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>

APA, Harvard, Vancouver, ISO, and other styles

37

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

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

38

Bai, Shuliang, and Linyuan Lu. "Turán Density of $2$-Edge-Colored Bipartite Graphs with Application on $\{2, 3\}$-Hypergraphs." Electronic Journal of Combinatorics 28, no. 3 (August 27, 2021). http://dx.doi.org/10.37236/10068.

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

39

Fujita, Shinya, Michitaka Furuya, András Gyárfás, and Ágnes Tóth. "Partition of Graphs and Hypergraphs into Monochromatic Connected Parts." Electronic Journal of Combinatorics 19, no. 3 (August 30, 2012). http://dx.doi.org/10.37236/2121.

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

40

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

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

41

Guo, Zhiwei, Christoph Brause, Maximilian Geißer, and Ingo Schiermeyer. "Compatible Spanning Circuits and Forbidden Induced Subgraphs." Graphs and Combinatorics 40, no. 1 (January 19, 2024). http://dx.doi.org/10.1007/s00373-023-02735-8.

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

42

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

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

43

Chen, He, and Xueliang Li. "Long Heterochromatic Paths in Edge-Colored Graphs." Electronic Journal of Combinatorics 12, no. 1 (July 29, 2005). http://dx.doi.org/10.37236/1930.

Full text

Abstract:

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$.

APA, Harvard, Vancouver, ISO, and other styles

44

Bowen, Matt, Adriana Hansberg, Amanda Montejano, and Alp Müyesser. "Colored Unavoidable Patterns and Balanceable Graphs." Electronic Journal of Combinatorics 31, no. 2 (May 3, 2024). http://dx.doi.org/10.37236/10571.

Full text

Abstract:

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}$.

APA, Harvard, Vancouver, ISO, and other styles

45

Maezawa, Shun-ichi, and Akiko Yazawa. "Special Case of Rota's Basis Conjecture on Graphic Matroids." Electronic Journal of Combinatorics 29, no. 3 (September 23, 2022). http://dx.doi.org/10.37236/10835.

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

46

Galeana-Sánchez, Hortensia, Felipe Hernández-Lorenzana, Rocío Sánchez-López, and 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, no. 2 (May 17, 2024). http://dx.doi.org/10.1007/s40590-024-00624-5.

Full text

Abstract:

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 .

APA, Harvard, Vancouver, ISO, and other styles

47

Fujita, Shinya, Atsushi Kaneko, Ingo Schiermeyer, and Kazuhiro Suzuki. "A Rainbow $k$-Matching in the Complete Graph with $r$ Colors." Electronic Journal of Combinatorics 16, no. 1 (April 30, 2009). http://dx.doi.org/10.37236/140.

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

48

Schaller, David, Manuel Lafond, Peter F. Stadler, Nicolas Wieseke, and Marc Hellmuth. "Indirect identification of horizontal gene transfer." Journal of Mathematical Biology 83, no. 1 (July 2021). http://dx.doi.org/10.1007/s00285-021-01631-0.

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

49

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

Full text

Abstract:

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$.

APA, Harvard, Vancouver, ISO, and other styles

50

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

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

Journal articles on the topic 'Edge-colored graph'

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles