Academic literature on the topic 'Edge-colored graph'
Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles
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 textAbstract:
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.
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 textAbstract:
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.
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 textAbstract:
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.
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 textAbstract:
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.
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 textAbstract:
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.
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 textAbstract:
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.
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 textAbstract:
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.
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 textAbstract:
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.
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
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 textAbstract:
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.
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 textAbstract:
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 finite maximally edge-colored directed graph is *Mn(C){ Mn(C(T))}k, where n is the number of vertices of the graph and k depends on the structure of the graph. Finally, we show that this algebra is in fact isomorphic to Mn(*C{ C(T)}k).
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 textAbstract:
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 structures locales peuvent être des appariements, des cliques, des cycles, des arbres, des sous-graphes couvrants (facteurs F, cycles Hamiltoniens), des familles d'intersection, des progressions arithmétiques, des solutions pour certaines équations (par exemple, x+y=z), des sous-graphes arc-en-ciel, etc. En particulier, la théorie des graphes extrémaux est une branche importante de la combinatoire extrémale, qui traite principalement de la manière dont les propriétés générales d'un graphe contrôlent la structure locale du graphe. Nous étudions l'existence d'un cycle Hamiltonien rainbow dans les systèmes de k-graphes, l'existence d'un appariement parfait rainbow dans les systèmes de k-graphes et l'existence d'un cycle long arc-en-ciel dans des graphes correctement colorés par les arêtesExtremal Combinatorics is one of the most vigorous branch of Combinatorial Mathematics in recent decades and it has been widely used in Computer Science, Network Design and Coding Design. It focuses on determining the maximum or minimum possible size of certain combinatorial structures, subject to certain conditions or constraints. The host sets could be graphs, digraphs, random graphs, hypergraphs, integers, primes, sets, edge-colored graphs and so on. The local structures could be matchings, cliques, cycles, trees, spanning subgraphs (F-factors, Hamilton cycles), intersecting families, arithmetic progressions, solutions for some equations (e.g. x₊y₌z), rainbow subgraphs and so on. In particular, Extremal Graph Theory is a significant branch of Extremal Combinatorics, which primarily explores how the overall properties of a graph influence its local structures. We study the existence of a rainbow Hamilton cycle in k-graph systems, the existence of rainbow perfect matching in k-graph systems, and the existence of long rainbow cycle in properly edge-colored graphs
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 textAbstract:
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 arêtes colorées est importante à la fois pour la théorie des graphes et pour d'autres sujets connexes. Nous étudions d'abord la condition de degré de couleur minimum forçant les triangles arc-en-ciel à sommets disjoints dans les graphes aux arêtes colorées. En 2013, Li s'est avéré être la meilleure condition de degré de couleur minimum possible pour l'existence d'un triangle arc-en-ciel. Motivés par cela, nous obtenons une condition de degré de couleur minimum précis garantissant l'existence de deux triangles arc-en-ciel à sommets disjoints et proposons une conjecture sur l'existence de k triangles arc-en-ciel à sommets disjoints. Deuxièmement, nous considérons la relation entre l'ordre de l'arbre maximum correctement coloré dans le graphe à bords colorés et le degré de couleur minimum. On obtient que pour un graphe connexe G aux arêtes colorées, l'ordre du maximum d'arbre correctement coloré est au moins \min\{|G|, 2\delta^{c}(G)\}, ce qui généralise un résultat de Cheng, Kano et Wang. De plus, la borne inférieure 2delta^{c}(G) dans notre résultat est la meilleure possible et nous caractérisons tous les graphes extrémaux. Troisièmement, nous recherchons la condition de degré de couleur minimum garantissant l'existence de 2-facteurs correctement colorés dans les graphes aux bords colorés. Nous dérivons une condition de degré de couleur minimum asymptotique forçant chaque facteur 2 correctement coloré avec exactement t composants, ce qui généralise un résultat de Lo. Nous déterminons également la meilleure condition de degré de couleur minimum possible pour l'existence d'un facteur 2 correctement coloré dans un graphe bipartite à arêtes colorées. Enfin, nous étudions les facteurs compatibles dans les graphes avec des systèmes d'incompatibilité. La notion de système d'incompatibilité a été introduite pour la première fois par Krivelevich, Lee et Sudakov, qui peut être considérée comme une mesure quantitative de la robustesse des propriétés du graphe. Récemment, il y a eu un intérêt croissant pour l'étude de la robustesse des propriétés des graphes, visant à renforcer les résultats classiques en théorie des graphes extrémaux et en combinatoire probabiliste. Nous étudions la version robuste du résultat d'Alon-- Yuster par rapport au système d'incompatibilitéIn this thesis, we study rainbow subgraphs and properly colored subgraphs in edge-colored graphs, and compatible subgraphs in gra-phs with incompatibility systems, which can be viewed as a generalization of edge-colored graphs. Compared with general graphs, edge-colored gra-phs contain more information and are able to model more complicated relations in communication net-work, social science, molecular biology and so on. Hence, the study of structures in edge-colored graphs is significant to both graph theory and other related subjects. We first study the minimum color degree condition forcing vertex-disjoint rainbow triangles in edge-colored graphs. In 2013, Li proved a best possible minimum color degree condition for the existence of a rainbow triangle. Motivated by this, we obtain a sharp minimum color degree condition guaran-teeing the existence of two vertex-disjoint rainbow triangles and propose a conjecture about the exis-tence of k vertex-disjoint rainbow triangles. Secondly, we consider the relation between the order of maximum properly colored tree in edge-colored graph and the minimum color degree. We obtain that for an edge-colored connected graph G, the order of maximum properly colored tree is at least \min\{|G|, 2\delta^{c}(G)\}, which generalizes a result of Cheng, Kano and Wang. Moreover, the lower bound 2delta^{c}(G) in our result is best possible and we characterize all extremal graphs. Thirdly, we research the minimum color degree condition guaranteeing the existence of properly colored 2-factors in edge-colored graphs. We derive an asymptotic minimum color degree con-dition forcing every properly colored 2-factor with exactly t components, which generalizes a result of Lo. We also determine the best possible mini-mum color degree condition for the existence of a properly colored 2-factor in an edge-colored bipartite graph. Finally, we study compatible factors in graphs with incompatibility systems. The notion of incom-patibility system was firstly introduced by Krivelevich, Lee and Sudakov, which can be viewed as a quantitative measure of robustness of graph properties. Recently, there has been an increasing interest in studying robustness of graph proper-ties, aiming to strengthen classical results in extremal graph theory and probabilistic combina-torics. We study the robust version of Alon--Yuster's result with respect to the incompatibility system
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 textAbstract:
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 chaque paire de sommets, ils existent $k$ chemins intérieurement sommet-disjoints. Nous prouvons plusieurs bornes supérieures pour $pc_k(G)$. Nous énonçons quelques conjectures pour les graphes généraux et bipartis et nous les prouvons dans le cas où $k = 1$. 2) Nous étudions l'existence de chaînes et de cycles hamiltoniens propres dans les multigraphes arêtes-coloriés. Nous établissons des conditions suffisantes, en fonction de plusieurs paramètres tels que le nombre d'arêtes, le degré arc-en-ciel, la connexité, etc. 3) Nous montrons que l'indice chromatique fort est linéaire au degré maximum pour tout graphe $k$-dégénéré où, $k$ est fixe. En corollaire, notre résultat conduit à une amélioration des constantes et donne également un algorithme plus simple et plus efficace pour cette famille de graphes. De plus, nous considérons les graphes planaires extérieurs. Nous donnons une formule pour trouver l'indice chromatique fort exact pour les graphes bipartis planaires extérieurs. Nous améliorons également la borne supérieure pour les graphes planaires extérieurs généraux. 4) Enfin, nous étudions les bicliques dans les graphes sans faux jumeaux et nous présentons ensuite un algorithme $O(n+m)$ pour reconnaître les graphes convergents et divergents en améliorant l'algorithme $O(n^4)$.
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 textAbstract:
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 l'existence de la PST dans des graphes arêtes-coloriés (pas forcément propre), en fonction de différents paramètres de graphes, tels que : nombre total de couleurs, la connectivité et le nombre d'arêtes incidentes dedifférentes couleurs pour un sommet. Nous nous intéressons aux chemins hamiltoniens proprement arêtes-coloriés dans le casdes multigraphes arêtes-coloriés. Ils présentent de l'intérêt pour notre étude, car ce sontégalement des arbres couvrants proprement arêtes-coloriés. Nous établissons des conditions suffisantes pour qu'un multigraphe contienne un chemin hamiltonien proprement arêtes-coloriés, en fonction de plusieurs paramètres tels que le nombre d'arêtes, le degré d'arêtes, etc. Puisque l'une des conditions suffisantes pour l'existence des arbres couvrants proprement arêtes-coloriés est la connectivité, nous prouvons plusieurs bornes supérieures pour le plus petit nombre de couleurs nécessaires pour la k-connectivité-propre. Nous énonçons plusieurs conjectures pour les graphes généraux et bipartis, et on arrive à les prouver pour k = 1.
6
Babu, Jasine. "Algorithmic and Combinatorial Questions on Some Geometric Problems on Graphs." Thesis, 2014. http://etd.iisc.ac.in/handle/2005/3485.
Full textAbstract:
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 algorithms or approximations. Our results include a polynomial time constant factor approximation algorithm for computing the cubicity of trees and a polynomial time constant (≤ 2.5) factor approximation algorithm for computing the boxicity of circular arc graphs. As far as we know, there were no constant factor approximation algorithms known previously, for computing boxicity or cubicity of any well known graph class for which the respective parameter value is unbounded.
We also obtained parameterized approximation algorithms for boxicity with various edit distance parameters. An o(n) factor approximation algorithm for computing the boxicity and cubicity of general graphs also evolved as an interesting corollary of one of these parameterized algorithms. This seems to be the first sub-linear factor approximation algorithm known for computing the boxicity and cubicity of general graphs.
Planar grid-drawings of outerplanar graphs: A graph is outerplanar, if it has a planar embedding with all its vertices lying on the outer face. We give an efficient algorithm to 2-vertex-connect any connected outerplanar graph G by adding more edges to it, in order to obtain a supergraph of G such that the resultant graph is still outerplanar and its pathwidth is within a constant times the pathwidth of G. This algorithm leads to a constant factor approximation algorithm for computing minimum height planar straight line grid-drawings of outerplanar graphs, extending the existing algorithm known for 2-vertex connected outerplanar graphs.
n−1
3
Maximum matchings in triangle distance Delaunay graphs: Delau-nay graphs of point sets are well studied in Computational Geometry. Instead of the Euclidean metric, if the Delaunay graph is defined with respect to the convex distance function defined by an equilateral triangle, it is called a Trian-gle Distance Delaunay graph. TD-Delaunay graphs are known to be equivalent to geometric spanners called half-Θ6 graphs.
It is known that classical Delaunay graphs of point sets always contain a near perfect matching, for non-degenerate point sets. We show that Triangle Distance Delaunay graphs of a set of n points in general position will always l m contain a matching of size and this bound is tight. We also show that Θ6 graphs, a class of supergraphs of half-Θ6 graphs, can have at most 5n − 11 edges, for point sets in general position.
Heterochromatic Paths in Edge Colored Graphs: Conditions on the coloring to guarantee the existence of long heterochromatic paths in edge col-ored graphs is a well explored problem in literature. The objective here is to obtain a good lower bound for λ(G) - the length of a maximum heterochro-matic path in an edge-colored graph G, in terms of ϑ(G) - the minimum color degree of G under the given coloring. There are graph families for which λ(G) = ϑ(G) − 1 under certain colorings, and it is conjectured that ϑ(G) − 1 is a tight lower bound for λ(G).
We show that if G has girth is at least 4 log2(ϑ(G))+2, then λ(G) ≥ ϑ(G)− 2. It is also proved that a weaker requirement that G just does not contain four-cycles is enough to guarantee that λ(G) is at least ϑ(G) −o(ϑ(G)). Other special cases considered include lower bounds for λ(G) in edge colored bipartite graphs, triangle-free graphs and graphs without heterochromatic triangles.
7
Babu, Jasine. "Algorithmic and Combinatorial Questions on Some Geometric Problems on Graphs." Thesis, 2014. http://etd.iisc.ernet.in/2005/3485.
Full textAbstract:
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 algorithms or approximations. Our results include a polynomial time constant factor approximation algorithm for computing the cubicity of trees and a polynomial time constant (≤ 2.5) factor approximation algorithm for computing the boxicity of circular arc graphs. As far as we know, there were no constant factor approximation algorithms known previously, for computing boxicity or cubicity of any well known graph class for which the respective parameter value is unbounded.
We also obtained parameterized approximation algorithms for boxicity with various edit distance parameters. An o(n) factor approximation algorithm for computing the boxicity and cubicity of general graphs also evolved as an interesting corollary of one of these parameterized algorithms. This seems to be the first sub-linear factor approximation algorithm known for computing the boxicity and cubicity of general graphs.
Planar grid-drawings of outerplanar graphs: A graph is outerplanar, if it has a planar embedding with all its vertices lying on the outer face. We give an efficient algorithm to 2-vertex-connect any connected outerplanar graph G by adding more edges to it, in order to obtain a supergraph of G such that the resultant graph is still outerplanar and its pathwidth is within a constant times the pathwidth of G. This algorithm leads to a constant factor approximation algorithm for computing minimum height planar straight line grid-drawings of outerplanar graphs, extending the existing algorithm known for 2-vertex connected outerplanar graphs.
n−1
3
Maximum matchings in triangle distance Delaunay graphs: Delau-nay graphs of point sets are well studied in Computational Geometry. Instead of the Euclidean metric, if the Delaunay graph is defined with respect to the convex distance function defined by an equilateral triangle, it is called a Trian-gle Distance Delaunay graph. TD-Delaunay graphs are known to be equivalent to geometric spanners called half-Θ6 graphs.
It is known that classical Delaunay graphs of point sets always contain a near perfect matching, for non-degenerate point sets. We show that Triangle Distance Delaunay graphs of a set of n points in general position will always l m contain a matching of size and this bound is tight. We also show that Θ6 graphs, a class of supergraphs of half-Θ6 graphs, can have at most 5n − 11 edges, for point sets in general position.
Heterochromatic Paths in Edge Colored Graphs: Conditions on the coloring to guarantee the existence of long heterochromatic paths in edge col-ored graphs is a well explored problem in literature. The objective here is to obtain a good lower bound for λ(G) - the length of a maximum heterochro-matic path in an edge-colored graph G, in terms of ϑ(G) - the minimum color degree of G under the given coloring. There are graph families for which λ(G) = ϑ(G) − 1 under certain colorings, and it is conjectured that ϑ(G) − 1 is a tight lower bound for λ(G).
We show that if G has girth is at least 4 log2(ϑ(G))+2, then λ(G) ≥ ϑ(G)− 2. It is also proved that a weaker requirement that G just does not contain four-cycles is enough to guarantee that λ(G) is at least ϑ(G) −o(ϑ(G)). Other special cases considered include lower bounds for λ(G) in edge colored bipartite graphs, triangle-free graphs and graphs without heterochromatic triangles.
8
Lo, Yuan-Hsun, and 羅元勳. "Multicolored Subgraphs in an Edge-colored Graphs." Thesis, 2010. http://ndltd.ncl.edu.tw/handle/34428885124296037709.
Full textAbstract:
博士國立交通大學
應用數學系所
98
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 proper (2m−1)-edge-coloring such that any two colors induce a 2-factor with each component a 4-cycle, then K2m can be partitioned into m isomorphic multicolored spanning trees. As a consequence, we show the existence of three isomorphic multicolored spanning trees whenever m≥14. As to the complete graph of odd order, two multicolored isomorphic unicyclic spanning subgraphs can be found in an arbitrary proper (2m+1)-edge-coloring of K{2m+1}. If we drop the condition “isomorphic”, we prove that there exist Ω(√m) mutually edge-disjoint multicolored spanning trees in any proper (2m−1)-edge-colored K_{2m} by applying a recursive construction. Using an analogous strategy, we can also find Ω(√m) mutually edge-disjoint multicolored unicyclic spanning subgraphs in any proper (2m−1)-edge-colored K_{2m−1}. Finally, we consider the problem of how to forbid a specific multicolored subgraph in a properly edge-colored complete bipartite graph. We (1) prove that for any integer k≥2, if n≥5k−6, then any properly n-edge-colored K_{k,n} contains a multicolored C2k, and (2) determine the order of the properly edge-colored complete bipartite graphs which forbid multicolored 6-cycles.
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, 315–26. Berlin, Heidelberg: Springer Berlin Heidelberg, 2008. http://dx.doi.org/10.1007/978-3-540-77537-9_31.
Full text
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, 319–25. Pisa: Scuola Normale Superiore, 2013. http://dx.doi.org/10.1007/978-88-7642-475-5_51.
Full text
3
Chinone, Kosuke, and Atsuyoshi Nakamura. "An Explainable Recommendation Based on Acyclic Paths in an Edge-Colored Graph." In Lecture Notes in Computer Science, 40–52. Cham: Springer International Publishing, 2022. http://dx.doi.org/10.1007/978-3-030-97546-3_4.
Full text
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, 353–71. Cham: Springer Nature Switzerland, 2023. http://dx.doi.org/10.1007/978-3-031-30820-8_22.
Full textAbstract:
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.
5
Lionni, Luca. "Colored Simplices and Edge-Colored Graphs." In Colored Discrete Spaces, 17–74. Cham: Springer International Publishing, 2018. http://dx.doi.org/10.1007/978-3-319-96023-4_2.
Full text
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, 50–61. Berlin, Heidelberg: Springer Berlin Heidelberg, 2013. http://dx.doi.org/10.1007/978-3-642-40313-2_7.
Full text
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, 248–59. Cham: Springer International Publishing, 2020. http://dx.doi.org/10.1007/978-3-030-38919-2_21.
Full text
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, 723–35. Berlin, Heidelberg: Springer Berlin Heidelberg, 2008. http://dx.doi.org/10.1007/978-3-540-78773-0_62.
Full text
9
Soifer, Alexander. "Edge Colored Graphs: Ramsey and Folkman Numbers." In The Mathematical Coloring Book, 242–60. New York, NY: Springer New York, 2009. http://dx.doi.org/10.1007/978-0-387-74642-5_27.
Full text
10
Soifer, Alexander. "Edge-Colored Graphs: Ramsey and Folkman Numbers." In The New Mathematical Coloring Book, 289–311. New York, NY: Springer US, 2024. http://dx.doi.org/10.1007/978-1-0716-3597-1_29.
Full textConference 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 textAbstract:
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 all unique feasible graphs for a select number of architecture problems, explicitly demonstrating the specific challenges of architecture design. Additional applications of this work to the larger architecture design process is also discussed.
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}. California: International Joint Conferences on Artificial Intelligence Organization, 2023. http://dx.doi.org/10.24963/ijcai.2023/227.
Full textAbstract:
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 based on Tutte's Theorem in graph theory as well as optimization techniques. Empirical results demonstrate that our encoding, in suitable languages with advanced SAT solvers, scales significantly better than a number of competing approaches on constrained-matching benchmarks. Our study identifies the necessity of designing problem-specific encodings when applying powerful general-purpose constraint solvers.
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}. California: International Joint Conferences on Artificial Intelligence Organization, 2023. http://dx.doi.org/10.24963/ijcai.2023/620.
Full textAbstract:
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-optimal. We show that LS-Max c-Cut presumably cannot be solved in g(k) · nᴼ⁽¹⁾ time even on bipartite graphs, for all c ≥ 2. We then show an algorithm for LS-Max c-Cut with running time O((3eΔ)ᵏ · c · k³ · Δ · n), where Δ is the maximum degree of the input graph. Finally, we evaluate the practical performance of this algorithm in a hill-climbing approach as a post-processing for state-of-the-art heuristics for Max c-Cut. We show that using parameterized local search, the results of this heuristic can be further improved on a set of standard benchmark instances.
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 textAbstract:
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.
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 textAbstract:
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.