Log in

Relevant bibliographies by topics / Edge-colored graph theory / Journal articles

To see the other types of publications on this topic, follow the link: Edge-colored graph theory.

Journal articles on the topic 'Edge-colored graph theory'

Author: Grafiati

Published: 14 December 2024

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

Select a source type:

Consult the top 50 journal articles for your research on the topic 'Edge-colored graph theory.'

Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.

You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.

Browse journal articles on a wide variety of disciplines and organise your bibliography correctly.

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

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

APA, Harvard, Vancouver, ISO, and other styles

3

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 additi

APA, Harvard, Vancouver, ISO, and other styles

4

Wang, Yiqiao, Juan Liu, Yongtang Shi, and Weifan Wang. "Star Chromatic Index of 1-Planar Graphs." Symmetry 14, no. 6 (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 produc

APA, Harvard, Vancouver, ISO, and other styles

5

Yin, Huixin, Miaomiao Han, and Murong Xu. "Strong Edge Coloring of K4(t)-Minor Free Graphs." Axioms 12, no. 6 (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 gr

APA, Harvard, Vancouver, ISO, and other styles

6

DINITZ, YEFIM, MATTHEW J. KATZ, and ROI KRAKOVSKI. "GUARDING RECTANGULAR PARTITIONS." International Journal of Computational Geometry & Applications 19, no. 06 (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 N

APA, Harvard, Vancouver, ISO, and other styles

7

Soulé, Antoine, Vladimir Reinharz, Roman Sarrazin-Gendron, Alain Denise, and Jérôme Waldispühl. "Finding recurrent RNA structural networks with fast maximal common subgraphs of edge-colored graphs." PLOS Computational Biology 17, no. 5 (2021): e1008990. http://dx.doi.org/10.1371/journal.pcbi.1008990.

Full text

Abstract:

RNA tertiary structure is crucial to its many non-coding molecular functions. RNA architecture is shaped by its secondary structure composed of stems, stacked canonical base pairs, enclosing loops. While stems are precisely captured by free-energy models, loops composed of non-canonical base pairs are not. Nor are distant interactions linking together those secondary structure elements (SSEs). Databases of conserved 3D geometries (a.k.a. modules) not captured by energetic models are leveraged for structure prediction and design, but the computational complexity has limited their study to local

APA, Harvard, Vancouver, ISO, and other styles

8

Wicaksono, Pramitha Shafika, and Kartono Kartono. "ANALISIS PENJADWALAN MATA PELAJARAN MENGGUNAKAN ALGORITMA WELCH-POWELL." Prismatika: Jurnal Pendidikan dan Riset Matematika 3, no. 1 (2020): 1–21. http://dx.doi.org/10.33503/prismatika.v3i1.1008.

Full text

Abstract:

At the beginning of each semester, subjects scheduling is always carried out by the curriculum representatives and academic staff. There were several problems that must be avoided in subjects scheduling, these problems were the schedule of teachers who teach one subject at the same time are scheduled in different classes, teachers who teach more than one subject are scheduled in the same class at the same time, teachers who are lack of scheduled for teaching. In the subject of graph theory, there is a concept of graph coloring, one of which is vertex coloring. In vertex coloring, there is a We

APA, Harvard, Vancouver, ISO, and other styles

9

Muranov, Yuri V., and Anna Szczepkowska. "Path homology theory of edge-colored graphs." Open Mathematics 19, no. 1 (2021): 706–23. http://dx.doi.org/10.1515/math-2021-0049.

Full text

Abstract:

Abstract In this paper, we introduce the category and the homotopy category of edge-colored digraphs and construct the functorial homology theory on the foundation of the path homology theory provided by Grigoryan, Muranov, and Shing-Tung Yau. We give the construction of the path homology theory for edge-colored graphs that follows immediately from the consideration of natural functor from the category of graphs to the subcategory of symmetrical digraphs. We describe the natural filtration of path homology groups of any digraph equipped with edge coloring, provide the definition of the corresp

APA, Harvard, Vancouver, ISO, and other styles

10

Lamken, Esther R., and Richard M. Wilson. "Decompositions of Edge-Colored Complete Graphs." Journal of Combinatorial Theory, Series A 89, no. 2 (2000): 149–200. http://dx.doi.org/10.1006/jcta.1999.3005.

Full text

APA, Harvard, Vancouver, ISO, and other styles

11

CASALI, MARIA RITA, and PAOLA CRISTOFORI. "A CATALOGUE OF ORIENTABLE 3-MANIFOLDS TRIANGULATED BY 30 COLORED TETRAHEDRA." Journal of Knot Theory and Its Ramifications 17, no. 05 (2008): 579–99. http://dx.doi.org/10.1142/s0218216508006312.

Full text

Abstract:

The present paper follows the computational approach to 3-manifold classification via edge-colored graphs, already performed in [1] (with respect to orientable 3-manifolds up to 28 colored tetrahedra), in [2] (with respect to non-orientable 3-manifolds up to 26 colored tetrahedra), in [3] and [4] (with respect to genus two 3-manifolds up to 34 colored tetrahedra): in fact, by automatic generation and analysis of suitable edge-colored graphs, called crystallizations, we obtain a catalogue of all orientable 3-manifolds admitting colored triangulations with 30 tetrahedra. These manifolds are unam

APA, Harvard, Vancouver, ISO, and other styles

12

Guśpiel, Grzegorz, and Grzegorz Gutowski. "Universal targets for homomorphisms of edge-colored graphs." Journal of Combinatorial Theory, Series B 127 (November 2017): 53–64. http://dx.doi.org/10.1016/j.jctb.2017.05.009.

Full text

APA, Harvard, Vancouver, ISO, and other styles

13

Dondi, Riccardo, and Florian Sikora. "Finding disjoint paths on edge-colored graphs: more tractability results." Journal of Combinatorial Optimization 36, no. 4 (2017): 1315–32. http://dx.doi.org/10.1007/s10878-017-0238-6.

Full text

APA, Harvard, Vancouver, ISO, and other styles

14

Sibley, Thomas Q. "On classifying finite edge colored graphs with two transitive automorphism groups." Journal of Combinatorial Theory, Series B 90, no. 1 (2004): 121–38. http://dx.doi.org/10.1016/s0095-8956(03)00079-0.

Full text

APA, Harvard, Vancouver, ISO, and other styles

15

Jin, Zemin, Mikio Kano, Xueliang Li, and Bing Wei. "Partitioning 2-edge-colored complete multipartite graphs into monochromatic cycles, paths and trees." Journal of Combinatorial Optimization 11, no. 4 (2006): 445–54. http://dx.doi.org/10.1007/s10878-006-8460-7.

Full text

APA, Harvard, Vancouver, ISO, and other styles

16

MUBAYI, DHRUV, and CAROLINE TERRY. "DISCRETE METRIC SPACES: STRUCTURE, ENUMERATION, AND 0-1 LAWS." Journal of Symbolic Logic 84, no. 4 (2019): 1293–325. http://dx.doi.org/10.1017/jsl.2019.52.

Full text

Abstract:

AbstractFix an integer $r \ge 3$. We consider metric spaces on n points such that the distance between any two points lies in $\left\{ {1, \ldots ,r} \right\}$. Our main result describes their approximate structure for large n. As a consequence, we show that the number of these metric spaces is $\left\lceil {{{r + 1} \over 2}} \right\rceil ^{\left( {\matrix{ n \cr 2 \cr } } \right) + o\left( {n^2 } \right)} .$Related results in the continuous setting have recently been proved by Kozma, Meyerovitch, Peled, and Samotij [34]. When r is even, our structural characterization is more precise and imp

APA, Harvard, Vancouver, ISO, and other styles

17

Casali, M. R., P. Cristofori, and C. Gagliardi. "PL 4-manifolds admitting simple crystallizations: framed links and regular genus." Journal of Knot Theory and Its Ramifications 25, no. 01 (2016): 1650005. http://dx.doi.org/10.1142/s021821651650005x.

Full text

Abstract:

Simple crystallizations are edge-colored graphs representing piecewise linear (PL) 4-manifolds with the property that the 1-skeleton of the associated triangulation equals the 1-skeleton of a 4-simplex. In this paper, we prove that any (simply-connected) PL 4-manifold [Formula: see text] admitting a simple crystallization admits a special handlebody decomposition, too; equivalently, [Formula: see text] may be represented by a framed link yielding [Formula: see text], with exactly [Formula: see text] components ([Formula: see text] being the second Betti number of [Formula: see text]). As a con

APA, Harvard, Vancouver, ISO, and other styles

18

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

APA, Harvard, Vancouver, ISO, and other styles

19

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

APA, Harvard, Vancouver, ISO, and other styles

20

Chen, He, and Xueliang Li. "Long Heterochromatic Paths in Edge-Colored Graphs." Electronic Journal of Combinatorics 12, no. 1 (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

APA, Harvard, Vancouver, ISO, and other styles

21

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

22

Maezawa, Shun-ichi, and Akiko Yazawa. "Special Case of Rota's Basis Conjecture on Graphic Matroids." Electronic Journal of Combinatorics 29, no. 3 (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 co

APA, Harvard, Vancouver, ISO, and other styles

23

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

24

Morawietz, Nils, Niels Grüttemeier, Christian Komusiewicz, and Frank Sommer. "Refined Parameterizations for Computing Colored Cuts in Edge-Colored Graphs." Theory of Computing Systems, September 22, 2022. http://dx.doi.org/10.1007/s00224-022-10101-z.

Full text

Abstract:

AbstractIn the NP-hard Colored (s,t)-Cut problem, the input is a graph G = (V,E) together with an edge-coloring ℓ : E → C, two vertices s and t, and a number k. The question is whether there is a set $S\subseteq C$ S ⊆ C of at most k colors such that deleting every edge with a color from S destroys all paths between s and t in G. We continue the study of the parameterized complexity of Colored (s,t)-Cut. First, we consider parameters related to the structure of G. For example, we study parameterization by the number ξi of edge deletions that are needed to transform G into a graph with maximum

APA, Harvard, Vancouver, ISO, and other styles

25

Kritschgau, Jürgen. "Rainbow Matchings of size $m$ in Graphs with Total Color Degree at least $2mn$." Electronic Journal of Combinatorics 27, no. 3 (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

26

Li, Xueliang, and Fengxia Liu. "Partitioning 3-Edge-Colored Complete Equi-Bipartite Graphs by Monochromatic Trees under a Color Degree Condition." Electronic Journal of Combinatorics 15, no. 1 (2008). http://dx.doi.org/10.37236/855.

Full text

Abstract:

The monochromatic tree partition number of an $r$-edge-colored graph $G$, denoted by $t_r(G)$, is the minimum integer $k$ such that whenever the edges of $G$ are colored with $r$ colors, the vertices of $G$ can be covered by at most $k$ vertex-disjoint monochromatic trees. In general, to determine this number is very difficult. For 2-edge-colored complete multipartite graph, Kaneko, Kano, and Suzuki gave the exact value of $t_2(K(n_1,n_2,\cdots,n_k))$. In this paper, we prove that if $n\geq 3$, and $K(n,n)$ is 3-edge-colored such that every vertex has color degree 3, then $t_3(K(n,n))=3$.

APA, Harvard, Vancouver, ISO, and other styles

27

Wang, Guanghui, and Hao Li. "Heterochromatic Matchings in Edge-Colored Graphs." Electronic Journal of Combinatorics 15, no. 1 (2008). http://dx.doi.org/10.37236/862.

Full text

Abstract:

Let $G$ be an (edge-)colored graph. A heterochromatic matching of $G$ is a matching in which no two edges have the same color. For a vertex $v$, let $d^c(v)$ be the color degree of $v$. We show that if $d^c(v)\geq k$ for every vertex $v$ of $G$, then $G$ has a heterochromatic matching of size $\big\lceil{5k-3\over 12}\big\rceil$. For a colored bipartite graph with bipartition $(X,Y)$, we prove that if it satisfies a Hall-like condition, then it has a heterochromatic matching of cardinality $\big\lceil{|X|\over 2}\big\rceil$, and we show that this bound is best possible.

APA, Harvard, Vancouver, ISO, and other styles

28

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

Full text

Abstract:

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

APA, Harvard, Vancouver, ISO, and other styles

29

Jin, Zemin, and Xueliang Li. "Anti-Ramsey Numbers for Graphs with Independent Cycles." Electronic Journal of Combinatorics 16, no. 1 (2009). http://dx.doi.org/10.37236/174.

Full text

Abstract:

An edge-colored graph is called rainbow if all the colors on its edges are distinct. Let ${\cal G}$ be a family of graphs. The anti-Ramsey number $AR(n,{\cal G})$ for ${\cal G}$, introduced by Erdős et al., is the maximum number of colors in an edge coloring of $K_n$ that has no rainbow copy of any graph in ${\cal G}$. In this paper, we determine the anti-Ramsey number $AR(n,\Omega_2)$, where $\Omega_2$ denotes the family of graphs that contain two independent cycles.

APA, Harvard, Vancouver, ISO, and other styles

30

Wang, Guanghui. "Rainbow Matchings in Properly Edge Colored Graphs." Electronic Journal of Combinatorics 18, no. 1 (2011). http://dx.doi.org/10.37236/649.

Full text

Abstract:

Let $G$ be a properly edge colored graph. A rainbow matching of $G$ is a matching in which no two edges have the same color. Let $\delta$ denote the minimum degree of $G$. We show that if $|V(G)|\geq \frac{8\delta}{5}$, then $G$ has a rainbow matching of size at least $\lfloor\frac {3 \delta }{5}\rfloor$. We also prove that if $G$ is a properly colored triangle-free graph, then $G$ has a rainbow matching of size at least $\lfloor\frac {2 \delta }{3}\rfloor$.

APA, Harvard, Vancouver, ISO, and other styles

31

Grech, Mariusz, and Andrzej Kisielewicz. "All totally symmetric colored graphs." Discrete Mathematics & Theoretical Computer Science Vol. 15 no. 1, Graph Theory (2013). http://dx.doi.org/10.46298/dmtcs.630.

Full text

Abstract:

Graph Theory International audience In this paper we describe all edge-colored graphs that are fully symmetric with respect to colors and transitive on every set of edges of the same color. They correspond to fully symmetric homogeneous factorizations of complete graphs. Our description completes the work done in our previous paper, where we have shown, in particular, that there are no such graphs with more than 5 colors. Using some recent results, with a help of computer, we settle all the cases that was left open in the previous paper.

APA, Harvard, Vancouver, ISO, and other styles

32

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

Full text

Abstract:

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

APA, Harvard, Vancouver, ISO, and other styles

33

Gyárfás, András, and Gábor Sárközy. "Large Monochromatic Components in Edge Colored Graphs with a Minimum Degree Condition." Electronic Journal of Combinatorics 24, no. 3 (2017). http://dx.doi.org/10.37236/7049.

Full text

Abstract:

It is well-known that in every $k$-coloring of the edges of the complete graph $K_n$ there is a monochromatic connected component of order at least ${n\over k-1}$. In this paper we study an extension of this problem by replacing complete graphs by graphs of large minimum degree. For $k=2$ the authors proved that $\delta(G)\ge{3n\over 4}$ ensures a monochromatic connected component with at least $\delta(G)+1$ vertices in every $2$-coloring of the edges of a graph $G$ with $n$ vertices. This result is sharp, thus for $k=2$ we really need a complete graph to guarantee that one of the colors has a

APA, Harvard, Vancouver, ISO, and other styles

34

Zhang, Xiaoyan, Zan-Bo Zhang, Hajo Broersma, and Xuelian Wen. "On the complexity of edge-colored subgraph partitioning problems in network optimization." Discrete Mathematics & Theoretical Computer Science Vol. 17 no. 3, Discrete Algorithms (2016). http://dx.doi.org/10.46298/dmtcs.2159.

Full text

Abstract:

International audience Network models allow one to deal with massive data sets using some standard concepts from graph theory. Understanding and investigating the structural properties of a certain data set is a crucial task in many practical applications of network optimization. Recently, labeled network optimization over colored graphs has been extensively studied. Given a (not necessarily properly) edge-colored graph $G=(V,E)$, a subgraph $H$ is said to be <i>monochromatic</i> if all its edges have the same color, and called <i>multicolored</i> if all its edges have

APA, Harvard, Vancouver, ISO, and other styles

35

Corsten, Jan, Louis DeBiasio, Ander Lamaison, and Richard Lang. "Upper density of monochromatic infinite paths." Advances in Combinatorics, October 30, 2019. http://dx.doi.org/10.19086/aic.10810.

Full text

Abstract:

Ramsey Theory investigates the existence of large monochromatic substructures. Unlike the most classical case of monochromatic complete subgraphs, the maximum guaranteed length of a monochromatic path in a two-edge-colored complete graph is well-understood. Gerencsér and Gyárfás in 1967 showed that any two-edge-coloring of a complete graph Kn contains a monochromatic path with ⌊2n/3⌋+1 vertices. The following two-edge-coloring shows that this is the best possible: partition the vertices of Kn into two sets A and B such that |A|=⌊n/3⌋ and |B|=⌈2n/3⌉, and color the edges between A and B red and

APA, Harvard, Vancouver, ISO, and other styles

36

Huang, Xiaolong, Hengzhe Li, Xueliang Li, and Yuefang Sun. "Oriented diameter and rainbow connection number of a graph." Discrete Mathematics & Theoretical Computer Science Vol. 16 no. 3, Graph Theory (2014). http://dx.doi.org/10.46298/dmtcs.2093.

Full text

Abstract:

Graph Theory International audience The oriented diameter of a bridgeless graph G is min diam(H) | H is a strang orientation of G. A path in an edge-colored graph G, where adjacent edges may have the same color, is called rainbow if no two edges of the path are colored the same. The rainbow connection number rc(G) of G is the smallest integer number k for which there exists a k-edge-coloring of G such that every two distinct vertices of G are connected by a rainbow path. In this paper, we obtain upper bounds for the oriented diameter and the rainbow connection number of a graph in terms of rad

APA, Harvard, Vancouver, ISO, and other styles

37

Gourvès, Laurent, Adria Lyra, Carlos A. Martinhon, and Jérôme Monnot. "On paths, trails and closed trails in edge-colored graphs." Discrete Mathematics & Theoretical Computer Science Vol. 14 no. 2, Graph Theory (2012). http://dx.doi.org/10.46298/dmtcs.586.

Full text

Abstract:

Graph Theory International audience In this paper we deal from an algorithmic perspective with different questions regarding properly edge-colored (or PEC) paths, trails and closed trails. Given a c-edge-colored graph G(c), we show how to polynomially determine, if any, a PEC closed trail subgraph whose number of visits at each vertex is specified before hand. As a consequence, we solve a number of interesting related problems. For instance, given subset S of vertices in G(c), we show how to maximize in polynomial time the number of S-restricted vertex (resp., edge) disjoint PEC paths (resp.,

APA, Harvard, Vancouver, ISO, and other styles

38

DeOrsey, Philip, Michael Ferrara, Nathan Graber, et al. "On the Strong Chromatic Index of Sparse Graphs." Electronic Journal of Combinatorics 25, no. 3 (2018). http://dx.doi.org/10.37236/5390.

Full text

Abstract:

The strong chromatic index of a graph $G$, denoted $\chi'_s(G)$, is the least number of colors needed to edge-color $G$ so that edges at distance at most two receive distinct colors. The strong list chromatic index, denoted $\chi'_{s,\ell}(G)$, is the least integer $k$ such that if arbitrary lists of size $k$ are assigned to each edge then $G$ can be edge-colored from those lists where edges at distance at most two receive distinct colors.We use the discharging method, the Combinatorial Nullstellensatz, and computation to show that if $G$ is a subcubic planar graph with ${\rm girth}(G) \geq 41

APA, Harvard, Vancouver, ISO, and other styles

39

Zaslavsky, Thomas. "A Mathematical Bibliography of Signed and Gain Graphs and Allied Areas." Electronic Journal of Combinatorics 1000 (December 21, 2018). http://dx.doi.org/10.37236/29.

Full text

Abstract:

A signed graph is a graph whose edges are labeled by signs. This is a bibliography of signed graphs and related mathematics.Several kinds of labelled graph have been called "signed" yet are mathematically very different. I distinguish four types:Group-signed graphs: the edge labels are elements of a 2-element group and are multiplied around a polygon (or along any walk). Among the natural generalizations are larger groups and vertex signs.Sign-colored graphs, in which the edges are labelled from a two-element set that is acted upon by the sign group: - interchanges labels, + leaves them unchan

APA, Harvard, Vancouver, ISO, and other styles

40

Galeana-Sánchez, Hortensia, Felipe Hernández-Lorenzana, and Rocío Sánchez-López. "Cycles of length 3 and 4 in edge-colored complete graphs with restrictions in the color transitions." Boletín de la Sociedad Matemática Mexicana 30, no. 3 (2024). http://dx.doi.org/10.1007/s40590-024-00645-0.

Full text

Abstract:

AbstractLet G be a graph and H a graph possibly with loops. We will say that a graph G is an H-colored graph if and only if there exists a function $$c:E(G)\longrightarrow V(H)$$ c : E ( G ) ⟶ V ( H ) . A cycle $$(v_1,\ldots ,v_k,v_1)$$ ( v 1 , … , v k , v 1 ) is an H-cycle if and only if $$(c(v_1 v_2),\ldots ,c(v_{k-1}v_k),$$ ( c ( v 1 v 2 ) , … , c ( v k - 1 v k ) , $$c(v_kv_1), c(v_1 v_2))$$ c ( v k v 1 ) , c ( v 1 v 2 ) ) is a walk in H. Whenever H is a complete graph without loops, an H-cycle is a properly colored cycle. In this paper, we work with an H-colored complete graph, namely G, w

APA, Harvard, Vancouver, ISO, and other styles

41

Winter, Martin. "Capturing Polytopal Symmetries by Coloring the Edge-Graph." Discrete & Computational Geometry, September 27, 2023. http://dx.doi.org/10.1007/s00454-023-00560-7.

Full text

Abstract:

AbstractA (convex) polytope $$P\subset \mathbb {R}^d$$ P ⊂ R d and its edge-graph $$G_P$$ G P can have very distinct symmetry properties, in that the edge-graph can be much more symmetric than the polytope. In this article we ask whether this can be “rectified” by coloring the vertices and edges of $$G_P$$ G P , that is, whether we can find such a coloring so that the combinatorial symmetry group of the colored edge-graph is actually isomorphic (in a natural way) to the linear or orthogonal symmetry group of the polytope. As it turns out, such colorings exist and some of them can be constructe

APA, Harvard, Vancouver, ISO, and other styles

42

Šámal, Robert, Amanda Montejano, Sebastián González Hermosillo de la Maza, Matt DeVos, and Ron Aharoni. "A rainbow version of Mantel's Theorem." Advances in Combinatorics, February 28, 2020. http://dx.doi.org/10.19086/aic.12043.

Full text

Abstract:

Mantel's Theorem from 1907 is one of the oldest results in graph theory: every simple $n$-vertex graph with more than $\frac{1}{4}n^2$ edges contains a triangle. The theorem has been generalized in many different ways, including other subgraphs, minimum degree conditions, etc. This article deals with a generalization to edge-colored multigraphs, which can be viewed as a union of simple graphs, each corresponding to an edge-color class. The case of two colors is the same as the original setting: Diwan and Mubayi proved that any two graphs $G_1$ and $G_2$ on the same set of $n$ vertices, each co

APA, Harvard, Vancouver, ISO, and other styles

43

Schaller, David, Tom Hartmann, Manuel Lafond, Peter F. Stadler, Nicolas Wieseke, and Marc Hellmuth. "Relative timing information and orthology in evolutionary scenarios." Algorithms for Molecular Biology 18, no. 1 (2023). http://dx.doi.org/10.1186/s13015-023-00240-4.

Full text

Abstract:

Abstract Background Evolutionary scenarios describing the evolution of a family of genes within a collection of species comprise the mapping of the vertices of a gene tree T to vertices and edges of a species tree S. The relative timing of the last common ancestors of two extant genes (leaves of T) and the last common ancestors of the two species (leaves of S) in which they reside is indicative of horizontal gene transfers (HGT) and ancient duplications. Orthologous gene pairs, on the other hand, require that their last common ancestors coincides with a corresponding speciation event. The rela

APA, Harvard, Vancouver, ISO, and other styles

44

Casselgren, Carl Johan, and Lan Anh Pham. "Restricted Extension of Sparse Partial Edge Colorings of Complete graphs." Electronic Journal of Combinatorics 28, no. 2 (2021). http://dx.doi.org/10.37236/9552.

Full text

Abstract:

Given a partial edge coloring of a complete graph $K_n$ and lists of allowed colors for the non-colored edges of $K_n$, can we extend the partial edge coloring to a proper edge coloring of $K_n$ using only colors from the lists? We prove that this question has a positive answer in the case when both the partial edge coloring and the color lists satisfy certain sparsity conditions.

APA, Harvard, Vancouver, ISO, and other styles

45

Song, Zi-Xia, and Jingmei Zhang. "On the Size of $(K_t,\mathcal{T}_k)$-Co-Critical Graphs." Electronic Journal of Combinatorics 28, no. 1 (2021). http://dx.doi.org/10.37236/8857.

Full text

Abstract:

Given an integer $r\geqslant 1$ and graphs $G, H_1, \ldots, H_r$, we write $G \rightarrow ({H}_1, \ldots, {H}_r)$ if every $r$-coloring of the edges of $G$ contains a monochromatic copy of $H_i$ in color $i$ for some $i\in\{1, \ldots, r\}$. A non-complete graph $G$ is $(H_1, \ldots, H_r)$-co-critical if $G \nrightarrow ({H}_1, \ldots, {H}_r)$, but $G+e\rightarrow ({H}_1, \ldots, {H}_r)$ for every edge $e$ in $\overline{G}$. In this paper, motivated by Hanson and Toft's conjecture [Edge-colored saturated graphs, J Graph Theory 11(1987), 191–196], we study the minimum number of edges over all $(

APA, Harvard, Vancouver, ISO, and other styles

46

Li, Deqiong, and Yaoping Hou. "Hypergraph Coverings and their Zeta Functions." Electronic Journal of Combinatorics 25, no. 4 (2018). http://dx.doi.org/10.37236/7764.

Full text

Abstract:

Let $H$ be a finite hypergraph. The concept of hypergraph coverings over $H$ is introduced, and we can generate all hypergraph coverings by permutation voltage assignments of the edge-colored graph or the incidence graph of $H$. Consequently, we show two explicit decomposition formulae for the zeta function of any hypergraph covering $\overline{H}$ over $H$ which indicates that the zeta function of $H$ divides the zeta function of $\overline{H}$.

APA, Harvard, Vancouver, ISO, and other styles

47

Chakraborti, Debsoumya, and Mihir Hasabnis. "The Threshold for the Full Perfect Matching Color Profile in a Random Coloring of Random Graphs." Electronic Journal of Combinatorics 28, no. 1 (2021). http://dx.doi.org/10.37236/9066.

Full text

Abstract:

Consider a graph $G$ with a coloring of its edge set $E(G)$ from a set $Q = \{c_1,c_2, \ldots, c_q\}$. Let $Q_i$ be the set of all edges colored with $c_i$. Recently, Frieze defined a notion of the perfect matching color profile denoted by $\mathrm{mcp}(G)$, which is the set of vectors $(m_1, m_2, \ldots, m_q)$ such that there exists a perfect matching $M$ in $G$ with $|Q_i \cap M| = m_i$ for all $i$. Let $\alpha_1, \alpha_2, \ldots, \alpha_q$ be positive constants such that $\sum_{i=1}^q \alpha_i = 1$. Let $G$ be the random bipartite graph $G_{n,n,p}$. Suppose the edges of $G$ are independent

APA, Harvard, Vancouver, ISO, and other styles

48

Frieze, Alan, and Charalampos E. Tsourakakis. "Rainbow Connection of Sparse Random Graphs." Electronic Journal of Combinatorics 19, no. 4 (2012). http://dx.doi.org/10.37236/2784.

Full text

Abstract:

An edge colored graph $G$ is rainbow edge connected if any two vertices are connected by a path whose edges have distinct colors. The rainbow connectivity of a connected graph $G$, denoted by $rc(G)$, is the smallest number of colors that are needed in order to make $G$ rainbow connected. In this work we study the rainbow connectivity of binomial random graphs at the connectivity threshold $p=\frac{\log n+\omega}{n}$ where $\omega=\omega(n)\to\infty$ and ${\omega}=o(\log{n})$ and of random $r$-regular graphs where $r \geq 3$ is a fixed integer. Specifically, we prove that the rainbow connectiv

APA, Harvard, Vancouver, ISO, and other styles

49

M. Lakshmi Kameswari, N. Naga MaruthiKumari, and T.V. Pradeep Kumar. "Journal of Pharmaceutical Negative Results ¦ Volume 13 ¦ Special Issue 6 ¦ 2022 1817 The Strongly Rainbow Connected Number of the Inverse Graphs." Journal of Pharmaceutical Negative Results, October 12, 2022, 1817–27. http://dx.doi.org/10.47750/pnr.2022.13.s06.239.

Full text

Abstract:

The two key parameters in this study of graph theory are the rainbow connected number and strongly rainbow connected numbers. The purpose of this study is to identify the strongly rainbow connected numbers of the inverse graphs corresponding to the modular groups under various operations, and to evaluate and explain the characteristics of these numbers in various contexts.The objective of this Study is to apply these concepts and results in the field of Networking and Coding. An edge colored graph G is called rainbow-connected if a path whose edges have different colors that connects any two v

APA, Harvard, Vancouver, ISO, and other styles

50

Charpentier, Clément, Reza Naserasr, and Éric Sopena. "Homomorphisms of Sparse Signed Graphs." Electronic Journal of Combinatorics 27, no. 3 (2020). http://dx.doi.org/10.37236/8478.

Full text

Abstract:

The notion of homomorphism of signed graphs, introduced quite recently, provides better interplay with the notion of minor and is thus of high importance in graph coloring. A newer, but equivalent, definition of homomorphisms of signed graphs, proposed jointly by the second and third authors of this paper and Thomas Zaslavsky, leads to a basic no-homomorphism lemma. According to this definition, a signed graph $(G, \sigma)$ admits a homomorphism to a signed graph $(H, \pi)$ if there is a mapping $\phi$ from the vertices and edges of $G$ to the vertices and edges of $H$ (respectively) which pre

APA, Harvard, Vancouver, ISO, and other styles

We offer discounts on all premium plans for authors whose works are included in thematic literature selections. Contact us to get a unique promo code!