Relevant bibliographies by topics / Edge-colored graph

Contents

  1. Journal articles
  2. Dissertations / Theses
  3. Book chapters
  4. Conference papers

Academic literature on the topic 'Edge-colored graph'

Author: Grafiati
Published: 25 May 2024

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

Select a source type:

Consult the lists of relevant articles, books, theses, conference reports, and other scholarly sources on the topic 'Edge-colored graph.'

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.

Journal articles on the topic "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 (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
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 (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
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 (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 additi
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 (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) b
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 (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 s
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 (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 (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 cont
APA, Harvard, Vancouver, ISO, and other styles

Dissertations / Theses on the topic "Edge-colored graph"

1

Brownlee, Erin Ann. "Maximally Edge-Colored Directed Graph Algebras." Thesis, North Dakota State University, 2017. https://hdl.handle.net/10365/28666.

Full text
Abstract:
Graph C*-algebras are constructed using projections corresponding to the vertices of the graph, and partial isometries corresponding to the edges of the graph. Here, we use the gauge-invariant uniqueness theorem to first establish that the C*-algebra of a graph composed of a directed cycle with finitely many edges emitting away from that cycle is Mn+k(C(T)), where n is the length of the cycle and k is the number of edges emitting away. We use this result to establish the main results of the thesis, which pertain to maximally edge-colored directed graphs. We show that the C*-algebra of any fini
APA, Harvard, Vancouver, ISO, and other styles
2

Wang, Bin. "Rainbow structures in properly edge-colored graphs and hypergraph systems." Electronic Thesis or Diss., université Paris-Saclay, 2024. http://www.theses.fr/2024UPASG016.

Full text
Abstract:
La combinatoire extrémale est l'une des branches les plus vigoureuses des mathématiques combinatoires au cours des dernières décennies, et elle a été largement utilisée en informatique, en conception de réseaux et en conception de codage. Elle se concentre sur la détermination de la taille maximale ou minimale possible de certaines structures combinatoires, sous certaines conditions ou contraintes. Les ensembles hôtes peuvent être des graphes, des digraphes, des graphes aléatoires, des hypergraphes, des entiers, des nombres premiers, des ensembles, des graphes avec arêtes colorées, etc. Les st
APA, Harvard, Vancouver, ISO, and other styles
3

Hu, Jie. "Rainbow subgraphs and properly colored subgraphs in colored graphs." Electronic Thesis or Diss., université Paris-Saclay, 2022. http://www.theses.fr/2022UPASG045.

Full text
Abstract:
Dans cette thèse, nous étudions les sous graphes arc-en-ciel et les sous-graphes correctement colorés dans les graphes à arêtes colorées, et les sous-graphes compatibles dans les graphes avec des systèmes d'incompatibilité, qui peuvent être considérés comme une généralisation des graphes à arêtes colorées. Par rapport aux graphes généraux, les graphes colorés contiennent plus d'informations et sont capables de modéliser des relations plus complexes dans les réseaux de communication, les sciences sociales, la biologie moléculaire, etc. Par conséquent, l'étude des structures dans les graphes aux
APA, Harvard, Vancouver, ISO, and other styles
4

Montero, Leandro Pedro. "Graphes et couleurs : graphes arêtes-coloriés, coloration d'arêtes et connexité propre." Phd thesis, Université Paris Sud - Paris XI, 2012. http://tel.archives-ouvertes.fr/tel-00776899.

Full text
Abstract:
Dans cette thèse nous étudions différents problèmes de graphes et multigraphes arêtes-coloriés tels que la connexité propre, la coloration forte d'arêtes et les chaînes et cycles hamiltoniens propres. Enfin, nous améliorons l'algorithme connu $O(n^4)$ pour décider du comportement d'un graphe sous opérateur biclique, en étudiant les bicliques dans les graphes sans faux jumeaux. Plus précisément, 1) Nous étudions d'abord le nombre $k$-connexité-propre des graphes, noté $pc_k(G)$, ç'est à dire le nombre minimum de couleurs nécessaires pour colorer les arêtes d'un graphe de façon à ce qu'entre cha
APA, Harvard, Vancouver, ISO, and other styles
5

Borozan, Valentin. "Proper and weak-proper trees in edges-colored graphs and multigraphs." Phd thesis, Université Paris Sud - Paris XI, 2011. http://tel.archives-ouvertes.fr/tel-00738959.

Full text
Abstract:
Dans la présente thèse nous étudions l'extraction d'arbres dans des graphes arêtes-coloriés.Nous nous concentrons sur la recherche d'arbres couvrants proprement arête-coloriés et faiblement arête-coloriés, notée PST et WST. Nous montrons que les versions d'optimisation de ces problèmes sont NP-Complete dans le cas général des graphes arêtes-coloriés, et nous proposons des algorithmes pour trouver ces arbres dans le cas des graphes arêtes-coloriés sans cycles proprement arêtes-coloriés.Nous donnons également quelques limites de nonapproximabilité. Nous proposons des conditions suffisantes pour
APA, Harvard, Vancouver, ISO, and other styles
6

Babu, Jasine. "Algorithmic and Combinatorial Questions on Some Geometric Problems on Graphs." Thesis, 2014. http://etd.iisc.ac.in/handle/2005/3485.

Full text
Abstract:
This thesis mainly focuses on algorithmic and combinatorial questions related to some geometric problems on graphs. In the last part of this thesis, a graph coloring problem is also discussed. Boxicity and Cubicity: These are graph parameters dealing with geomet-ric representations of graphs in higher dimensions. Both these parameters are known to be NP-Hard to compute in general and are even hard to approximate within an O(n1− ) factor for any > 0, under standard complexity theoretic assumptions. We studied algorithmic questions for these problems, for certain graph classes, to yield efficient
APA, Harvard, Vancouver, ISO, and other styles
7

Babu, Jasine. "Algorithmic and Combinatorial Questions on Some Geometric Problems on Graphs." Thesis, 2014. http://etd.iisc.ernet.in/2005/3485.

Full text
Abstract:
This thesis mainly focuses on algorithmic and combinatorial questions related to some geometric problems on graphs. In the last part of this thesis, a graph coloring problem is also discussed. Boxicity and Cubicity: These are graph parameters dealing with geomet-ric representations of graphs in higher dimensions. Both these parameters are known to be NP-Hard to compute in general and are even hard to approximate within an O(n1− ) factor for any > 0, under standard complexity theoretic assumptions. We studied algorithmic questions for these problems, for certain graph classes, to yield efficient
APA, Harvard, Vancouver, ISO, and other styles
8

Lo, Yuan-Hsun, and 羅元勳. "Multicolored Subgraphs in an Edge-colored Graphs." Thesis, 2010. http://ndltd.ncl.edu.tw/handle/34428885124296037709.

Full text
Abstract:
博士<br>國立交通大學<br>應用數學系所<br>98<br>A subgraph in an edge-colored graph is multicolored if all its edges receive distinct colors. In this dissertation, we first prove that a complete graph of order 2m (m≠2) can be properly edge-colored with 2m−1 colors in such a way that the edges of K_{2m} can be partitioned into m isomorphic multicolored spanning trees. Then, for the complete graph on 2m+1 vertices, we give a proper edge-coloring with 2m+1 colors such that the edges of K{2m+1} can be partitioned into m multicolored Hamiltonian cycles. In the second part, we first prove that if K_{2m} admits a p
APA, Harvard, Vancouver, ISO, and other styles

Book chapters on the topic "Edge-colored graph"

1

Di Giacomo, Emilio, Giuseppe Liotta, and Francesco Trotta. "Drawing Colored Graphs with Constrained Vertex Positions and Few Bends per Edge." In Graph Drawing. Springer Berlin Heidelberg, 2008. http://dx.doi.org/10.1007/978-3-540-77537-9_31.

Full text
APA, Harvard, Vancouver, ISO, and other styles
2

Das, Anita, P. Suresh, and S. V. Subrahmanya. "Rainbow path and minimum degree in properly edge colored graphs." In The Seventh European Conference on Combinatorics, Graph Theory and Applications. Scuola Normale Superiore, 2013. http://dx.doi.org/10.1007/978-88-7642-475-5_51.

Full text
APA, Harvard, Vancouver, ISO, and other styles
3

Chinone, Kosuke, and Atsuyoshi Nakamura. "An Explainable Recommendation Based on Acyclic Paths in an Edge-Colored Graph." In Lecture Notes in Computer Science. Springer International Publishing, 2022. http://dx.doi.org/10.1007/978-3-030-97546-3_4.

Full text
APA, Harvard, Vancouver, ISO, and other styles
4

Larsen, Casper Abild, Simon Meldahl Schmidt, Jesper Steensgaard, Anna Blume Jakobsen, Jaco van de Pol, and Andreas Pavlogiannis. "A Truly Symbolic Linear-Time Algorithm for SCC Decomposition." In Tools and Algorithms for the Construction and Analysis of Systems. Springer Nature Switzerland, 2023. http://dx.doi.org/10.1007/978-3-031-30820-8_22.

Full text
Abstract:
AbstractDecomposing a directed graph to its strongly connected components (SCCs) is a fundamental task in model checking. To deal with the state-space explosion problem, graphs are often represented symbolically using binary decision diagrams (BDDs), which have exponential compression capabilities. The theoretically-best symbolic algorithm for SCC decomposition is Gentilini et al’s $$\textsc {Skeleton}$$ S K E L E T O N algorithm, that uses O(n) symbolic steps on a graph of n nodes. However, $$\textsc {Skeleton}$$ S K E L E T O N uses $$\Theta (n)$$ Θ ( n ) symbolic objects, as opposed to (poly-)logarithmically many, which is the norm for symbolic algorithms, thereby relinquishing its symbolic nature. Here we present $$\textsc {Chain}$$ C H A I N , a new symbolic algorithm for SCC decomposition that also makes O(n) symbolic steps, but further uses logarithmic space, and is thus truly symbolic. We then extend $$\textsc {Chain}$$ C H A I N to $$\textsc {ColoredChain}$$ C O L O R E D C H A I N , an algorithm for SCC decomposition on edge-colored graphs, which arise naturally in model-checking a family of systems. Finally, we perform an experimental evaluation of $$\textsc {Chain}$$ C H A I N among other standard symbolic SCC algorithms in the literature. The results show that $$\textsc {Chain}$$ C H A I N is competitive on almost all benchmarks, and often faster, while it clearly outperforms all other algorithms on challenging inputs.
APA, Harvard, Vancouver, ISO, and other styles
5

Lionni, Luca. "Colored Simplices and Edge-Colored Graphs." In Colored Discrete Spaces. Springer International Publishing, 2018. http://dx.doi.org/10.1007/978-3-319-96023-4_2.

Full text
APA, Harvard, Vancouver, ISO, and other styles
6

Angel, Eric, Evripidis Bampis, Alexander Kononov, Dimitris Paparas, Emmanouil Pountourakis, and Vassilis Zissimopoulos. "Clustering on k-Edge-Colored Graphs." In Mathematical Foundations of Computer Science 2013. Springer Berlin Heidelberg, 2013. http://dx.doi.org/10.1007/978-3-642-40313-2_7.

Full text
APA, Harvard, Vancouver, ISO, and other styles
7

Morawietz, Nils, Niels Grüttemeier, Christian Komusiewicz, and Frank Sommer. "Refined Parameterizations for Computing Colored Cuts in Edge-Colored Graphs." In SOFSEM 2020: Theory and Practice of Computer Science. Springer International Publishing, 2020. http://dx.doi.org/10.1007/978-3-030-38919-2_21.

Full text
APA, Harvard, Vancouver, ISO, and other styles
8

Abouelaoualim, A., K. Ch Das, L. Faria, Y. Manoussakis, C. Martinhon, and R. Saad. "Paths and Trails in Edge-Colored Graphs." In Lecture Notes in Computer Science. Springer Berlin Heidelberg, 2008. http://dx.doi.org/10.1007/978-3-540-78773-0_62.

Full text
APA, Harvard, Vancouver, ISO, and other styles
9

Soifer, Alexander. "Edge Colored Graphs: Ramsey and Folkman Numbers." In The Mathematical Coloring Book. Springer New York, 2009. http://dx.doi.org/10.1007/978-0-387-74642-5_27.

Full text
APA, Harvard, Vancouver, ISO, and other styles
10

Soifer, Alexander. "Edge-Colored Graphs: Ramsey and Folkman Numbers." In The New Mathematical Coloring Book. Springer US, 2024. http://dx.doi.org/10.1007/978-1-0716-3597-1_29.

Full text
APA, Harvard, Vancouver, ISO, and other styles

Conference papers on the topic "Edge-colored graph"

1

Herber, Daniel R., Tinghao Guo, and James T. Allison. "Enumeration of Architectures With Perfect Matchings." In ASME 2016 International Design Engineering Technical Conferences and Computers and Information in Engineering Conference. American Society of Mechanical Engineers, 2016. http://dx.doi.org/10.1115/detc2016-60212.

Full text
Abstract:
In this article a class of architecture design problems is explored with perfect matchings. A perfect matching in a graph is a set of edges such that every vertex is present in exactly one edge. The perfect matching approach has many desirable properties such as complete design space coverage. Improving on the pure perfect matching approach, a tree search algorithm is developed that more efficiently covers the same design space. The effect of specific network structure constraints and colored graph isomorphisms on the desired design space is demonstrated. This is accomplished by determining al
APA, Harvard, Vancouver, ISO, and other styles
2

Vardi, Moshe Y., and Zhiwei Zhang. "Solving Quantum-Inspired Perfect Matching Problems via Tutte-Theorem-Based Hybrid Boolean Constraints." In Thirty-Second International Joint Conference on Artificial Intelligence {IJCAI-23}. International Joint Conferences on Artificial Intelligence Organization, 2023. http://dx.doi.org/10.24963/ijcai.2023/227.

Full text
Abstract:
Determining the satisfiability of Boolean constraint-satisfaction problems with different types of constraints, that is hybrid constraints, is a well-studied problem with important applications. We study a new application of hybrid Boolean constraints, which arises in quantum computing. The problem relates to constrained perfect matching in edge-colored graphs. While general-purpose hybrid constraint solvers can be powerful, we show that direct encodings of the constrained-matching problem as hybrid constraints scale poorly and special techniques are still needed. We propose a novel encoding b
APA, Harvard, Vancouver, ISO, and other styles
3

Garvardt, Jaroslav, Niels Grüttemeier, Christian Komusiewicz, and Nils Morawietz. "Parameterized Local Search for Max c-Cut." In Thirty-Second International Joint Conference on Artificial Intelligence {IJCAI-23}. International Joint Conferences on Artificial Intelligence Organization, 2023. http://dx.doi.org/10.24963/ijcai.2023/620.

Full text
Abstract:
In the NP-hard Max c-Cut problem, one is given an undirected edge-weighted graph G and wants to color the vertices of G with c colors such that the total weight of edges with distinctly colored endpoints is maximal. The case with c=2 is the famous Max Cut problem. To deal with the NP-hardness of this problem, we study parameterized local search algorithms. More precisely, we study LS-Max c-Cut where we are additionally given a vertex coloring f and an integer k and the task is to find a better coloring f' that differs from f in at most k entries, if such a coloring exists; otherwise, f is k-op
APA, Harvard, Vancouver, ISO, and other styles
4

Faria, Luerbio, Sulamita Klein, Ignasi Sau, Uéverton S. Souza, and Rubens Sucupira. "On Colored Edge Cuts in Graphs." In I Encontro de Teoria da Computação. Sociedade Brasileira de Computação - SBC, 2018. http://dx.doi.org/10.5753/etc.2016.9764.

Full text
Abstract:
In this work we present some results on the classical and parameterized complexity of finding cuts in edge-colored graphs. In general, we are interested in problems of finding cuts {A,B} which minimize or maximize the number of colors occurring in the edges with exactly one endpoint in A.&#x0D;
APA, Harvard, Vancouver, ISO, and other styles
5

Botler, Fábio, Lucas Colucci, Paulo Matias, Guilherme Mota, Roberto Parente, and Matheus Secco. "Proper edge colorings of complete graphs without repeated triangles." In Encontro de Teoria da Computação. Sociedade Brasileira de Computação - SBC, 2022. http://dx.doi.org/10.5753/etc.2022.222917.

Full text
Abstract:
In this paper, we consider the problem of computing the minimum number of colors needed to properly color the edges of a complete graph on $n$ vertices so that there are no pair of vertex-disjoint triangles colored with the same colors. This problem was introduced recently (in a more general context) by Conlon and Tyomkyn, and the corresponding value was known for odd $n$. We compute this number for another infinite set of values of $n$, and discuss some small cases.
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!

To the bibliography