Relevant bibliographies by topics / Edge-colored graph theory

Contents

  1. Journal articles

Academic literature 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 lists of relevant articles, books, theses, conference reports, and other scholarly sources 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.

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

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 established. In this paper, we consider the existence of (more general) compatible spanning circuits from an algorithmic perspective. We first show that determining whether an edge-colored connected graph contains a compatible spanning circuit is an NP-complete problem. Next, we describe two polynomial-time algorithms for finding compatible spanning circuits in edge-colored complete graphs. These results in some sense give partial support to a conjecture on the existence of compatible Hamilton cycles in edge-colored complete graphs due to Bollobás and Erdős from the 1970s.
APA, Harvard, Vancouver, ISO, and other styles
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 additional vertices. System reflected by graph G(Σ) can work even if there are k faults of its objects. Complete graph is a graph where each two vertices have an edge between them. Complete graphs have no edge extensions because there is no way to add additional edge to the graph with a maximum number of edges. In other words, the system reflected by some complete graph cannot be able to resist connection faults. Therefore the article research is focused on vertex extensions only. There is a description of vertex extensions existence condition for those colored complete graphs. This paper considers generating schemes for such minimal vertex extensions along with formulas, which allows to calculate number of additional edges to have an ability to construct minimal vertex extension.
APA, Harvard, Vancouver, ISO, and other styles
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 produced. A graph G is called 1-planar if it can be drawn in the plane such that each edge crosses at most one other edge. In this paper, we prove that every 1-planar graph G satisfies χst′(G)≤7.75Δ+166; and moreover χst′(G)≤⌊1.5Δ⌋+500 if G contains no 4-cycles, and χst′(G)≤2.75Δ+116 if G is 3-connected, or optimal, or NIC-planar.
APA, Harvard, Vancouver, ISO, and other styles
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 graphs by Batenburg, Joannis de Verclos, Kang, Pirot in 2022 and Wang, Wang, and Wang in 2018. These upper bounds are sharp.
APA, Harvard, Vancouver, ISO, and other styles
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 NP-hard. For edge guards, we prove that guarding all rectangles, where guards are restricted to a given subset of the edges, is NP-hard. For both results we show a reduction from vertex cover in non-bipartite 3-connected cubic planar graphs of girth greater than three. For the second NP-hardness result, we obtain a graph-theoretic result which establishes a connection between the set of faces of a plane graph of vertex degree at most three and a vertex cover for this graph. More precisely, we prove that one can assign to each internal face a distinct vertex of the cover, which lies on the face's boundary. We show that the vertices of a rectangular partition can be colored red, green, or black, such that each rectangle has all three colors on its boundary. We conjecture that the above is also true for four colors. Finally, we obtain a worst-case upper bound on the number of edge guards that are sufficient for guarding rectangular partitions with some restrictions on their structure.
APA, Harvard, Vancouver, ISO, and other styles
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 elements, loops. Representing the RNA structure as a graph has recently allowed to expend this work to pairs of SSEs, uncovering a hierarchical organization of these 3D modules, at great computational cost. Systematically capturing recurrent patterns on a large scale is a main challenge in the study of RNA structures. In this paper, we present an efficient algorithm to compute maximal isomorphisms in edge colored graphs. We extend this algorithm to a framework well suited to identify RNA modules, and fast enough to considerably generalize previous approaches. To exhibit the versatility of our framework, we first reproduce results identifying all common modules spanning more than 2 SSEs, in a few hours instead of weeks. The efficiency of our new algorithm is demonstrated by computing the maximal modules between any pair of entire RNA in the non-redundant corpus of known RNA 3D structures. We observe that the biggest modules our method uncovers compose large shared sub-structure spanning hundreds of nucleotides and base pairs between the ribosomes of Thermus thermophilus, Escherichia Coli, and Pseudomonas aeruginosa.
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 Welch-Powell Algorithm application which produces a color for each vertex. In subject scheduling, it is assumed that the vertex is the subject and the teacher, while the edge is the class. In vertex coloring, graph vertices are colored so that there's no two neighboring vertices have the same color. The aim of this research was to arrange a lesson schedule so that problems do not occur such as clashes between teachers, subjects, and teaching hours. The method used in arranging this lesson schedule used the Welch-Powell Algorithm. The results obtained were using the Welch-Powell Algorithm to produce a lesson schedule every day where if there are two classes that have the same subject, they can meet the same day requirements but come in different hours and get a lesson schedule that has no clash between teachers, subjects, and teaching hours.
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 corresponding spectral sequence, and obtain commutative diagrams and braids of exact sequences.
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
More sources
You might also be interested in the extended bibliographies on the topic 'Edge-colored graph theory' for particular source types:
Journal articles
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