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'
Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles
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 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
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.
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 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.
4
Wang, Yiqiao, Juan Liu, Yongtang Shi, and Weifan Wang. "Star Chromatic Index of 1-Planar Graphs." Symmetry 14, no. 6 (June 8, 2022): 1177. http://dx.doi.org/10.3390/sym14061177.
Full textAbstract:
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.
5
Yin, Huixin, Miaomiao Han, and Murong Xu. "Strong Edge Coloring of K4(t)-Minor Free Graphs." Axioms 12, no. 6 (June 5, 2023): 556. http://dx.doi.org/10.3390/axioms12060556.
Full textAbstract:
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.
6
DINITZ, YEFIM, MATTHEW J. KATZ, and ROI KRAKOVSKI. "GUARDING RECTANGULAR PARTITIONS." International Journal of Computational Geometry & Applications 19, no. 06 (December 2009): 579–94. http://dx.doi.org/10.1142/s0218195909003131.
Full textAbstract:
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.
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 (May 28, 2021): e1008990. http://dx.doi.org/10.1371/journal.pcbi.1008990.
Full textAbstract:
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.
8
Wicaksono, Pramitha Shafika, and Kartono Kartono. "ANALISIS PENJADWALAN MATA PELAJARAN MENGGUNAKAN ALGORITMA WELCH-POWELL." Prismatika: Jurnal Pendidikan dan Riset Matematika 3, no. 1 (October 27, 2020): 1–21. http://dx.doi.org/10.33503/prismatika.v3i1.1008.
Full textAbstract:
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.
9
Muranov, Yuri V., and Anna Szczepkowska. "Path homology theory of edge-colored graphs." Open Mathematics 19, no. 1 (January 1, 2021): 706–23. http://dx.doi.org/10.1515/math-2021-0049.
Full textAbstract:
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.
10
Lamken, Esther R., and Richard M. Wilson. "Decompositions of Edge-Colored Complete Graphs." Journal of Combinatorial Theory, Series A 89, no. 2 (February 2000): 149–200. http://dx.doi.org/10.1006/jcta.1999.3005.
Full text
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 (May 2008): 579–99. http://dx.doi.org/10.1142/s0218216508006312.
Full textAbstract:
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 unambiguously identified via JSJ decompositions and fibering structures. It is worth noting that, in the present work, a suitable use of elementary combinatorial moves yields an automatic partition of the elements of the generated crystallization catalogue into equivalence classes, which turn out to be in one-to-one correspondence with the homeomorphism classes of the represented manifolds.
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
13
Dondi, Riccardo, and Florian Sikora. "Finding disjoint paths on edge-colored graphs: more tractability results." Journal of Combinatorial Optimization 36, no. 4 (December 14, 2017): 1315–32. http://dx.doi.org/10.1007/s10878-017-0238-6.
Full text
14
Sibley, Thomas Q. "On classifying finite edge colored graphs with two transitive automorphism groups." Journal of Combinatorial Theory, Series B 90, no. 1 (January 2004): 121–38. http://dx.doi.org/10.1016/s0095-8956(03)00079-0.
Full text
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 (May 17, 2006): 445–54. http://dx.doi.org/10.1007/s10878-006-8460-7.
Full text
16
MUBAYI, DHRUV, and CAROLINE TERRY. "DISCRETE METRIC SPACES: STRUCTURE, ENUMERATION, AND 0-1 LAWS." Journal of Symbolic Logic 84, no. 4 (August 19, 2019): 1293–325. http://dx.doi.org/10.1017/jsl.2019.52.
Full textAbstract:
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 implies that almost all such metric spaces have all distances at least $r/2$. As an easy consequence, when r is even, we improve the error term above from $o\left( {n^2 } \right)$ to $o\left( 1 \right)$, and also show a labeled first-order 0-1 law in the language ${\cal L}_r $, consisting of r binary relations, one for each element of $[r]$ . In particular, we show the almost sure theory T is the theory of the Fraïssé limit of the class of all finite simple complete edge-colored graphs with edge colors in $\left\{ {r/2, \ldots ,r} \right\}$.Our work can be viewed as an extension of a long line of research in extremal combinatorics to the colored setting, as well as an addition to the collection of known structures that admit logical 0-1 laws.
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 (January 2016): 1650005. http://dx.doi.org/10.1142/s021821651650005x.
Full textAbstract:
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 consequence, the regular genus of [Formula: see text] is proved to be the double of [Formula: see text]. Moreover, the characterization of any such PL 4-manifold by [Formula: see text], where [Formula: see text] is the gem-complexity of [Formula: see text] (i.e. the non-negative number [Formula: see text], [Formula: see text] being the minimum order of a crystallization of [Formula: see text]), implies that both PL invariants gem-complexity and regular genus turn out to be additive within the class of all PL 4-manifolds admitting simple crystallizations (in particular, within the class of all “standard” simply-connected PL 4-manifolds).
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 (August 27, 2021). http://dx.doi.org/10.37236/10068.
Full textAbstract:
We consider the Turán problems of $2$-edge-colored graphs. A $2$-edge-colored graph $H=(V, E_r, E_b)$ is a triple consisting of the vertex set $V$, the set of red edges $E_r$ and the set of blue edges $E_b$ where $E_r$ and $E_b$ do not have to be disjoint. The Turán density $\pi(H)$ of $H$ is defined to be $\lim_{n\to\infty} \max_{G_n}h_n(G_n)$, where $G_n$ is chosen among all possible $2$-edge-colored graphs on $n$ vertices containing no $H$ as a sub-graph and $h_n(G_n)=(|E_r(G)|+|E_b(G)|)/\binom{n}{2}$ is the formula to measure the edge density of $G_n$. We will determine the Turán densities of all $2$-edge-colored bipartite graphs. We also give an important application on the Turán problems of $\{2, 3\}$-hypergraphs.
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 (August 30, 2012). http://dx.doi.org/10.37236/2121.
Full textAbstract:
We show that two results on covering of edge colored graphs by monochromatic connected parts can be extended to partitioning. We prove that for any $2$-edge-colored non-trivial $r$-uniform hypergraph $H$, the vertex set can be partitioned into at most $\alpha (H)-r+2$ monochromatic connected parts, where $\alpha (H)$ is the maximum number of vertices that does not contain any edge. In particular, any $2$-edge-colored graph $G$ can be partitioned into $\alpha(G)$ monochromatic connected parts, where $\alpha (G)$ denotes the independence number of $G$. This extends König's theorem, a special case of Ryser's conjecture. Our second result is about Gallai-colorings, i.e. edge-colorings of graphs without $3$-edge-colored triangles. We show that for any Gallai-coloring of a graph $G$, the vertex set of $G$ can be partitioned into monochromatic connected parts, where the number of parts depends only on $\alpha(G)$. This extends its cover-version proved earlier by Simonyi and two of the authors.
20
Chen, He, and Xueliang Li. "Long Heterochromatic Paths in Edge-Colored Graphs." Electronic Journal of Combinatorics 12, no. 1 (July 29, 2005). http://dx.doi.org/10.37236/1930.
Full textAbstract:
Let $G$ be an edge-colored graph. A heterochromatic path of $G$ is such a path in which no two edges have the same color. $d^c(v)$ denotes the color degree of a vertex $v$ of $G$. In a previous paper, we showed that if $d^c(v)\geq k$ for every vertex $v$ of $G$, then $G$ has a heterochromatic path of length at least $\lceil{k+1\over 2}\rceil$. It is easy to see that if $k=1,2$, $G$ has a heterochromatic path of length at least $k$. Saito conjectured that under the color degree condition $G$ has a heterochromatic path of length at least $\lceil{2k+1\over 3}\rceil$. Even if this is true, no one knows if it is a best possible lower bound. Although we cannot prove Saito's conjecture, we can show in this paper that if $3\leq k\leq 7$, $G$ has a heterochromatic path of length at least $k-1,$ and if $k\geq 8$, $G$ has a heterochromatic path of length at least $\lceil{3k\over 5}\rceil+1$. Actually, we can show that for $1\leq k\leq 5$ any graph $G$ under the color degree condition has a heterochromatic path of length at least $k$, with only one exceptional graph $K_4$ for $k=3$, one exceptional graph for $k=4$ and three exceptional graphs for $k=5$, for which $G$ has a heterochromatic path of length at least $k-1$. Our experience suggests us to conjecture that under the color degree condition $G$ has a heterochromatic path of length at least $k-1$.
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 (April 30, 2009). http://dx.doi.org/10.37236/140.
Full textAbstract:
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.
22
Maezawa, Shun-ichi, and Akiko Yazawa. "Special Case of Rota's Basis Conjecture on Graphic Matroids." Electronic Journal of Combinatorics 29, no. 3 (September 23, 2022). http://dx.doi.org/10.37236/10835.
Full textAbstract:
Gian-Carlo Rota conjectured that for any $n$ bases $B_1,B_2,\ldots,B_n$ in a matroid of rank $n$, there exist $n$ disjoint transversal bases of $B_1,B_2,\ldots,B_n$. The conjecture for graphic matroids corresponds to the problem of an edge-decomposition as follows; If an edge-colored connected multigraph $G$ has $n-1$ colors and the graph induced by the edges colored with $c$ is a spanning tree for each color $c$, then $G$ has $n-1$ mutually edge-disjoint rainbow spanning trees. In this paper, we prove that edge-colored graphs where the edges colored with $c$ induce a spanning star for each color $c$ can be decomposed into rainbow spanning trees.
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 (June 28, 2012). http://dx.doi.org/10.37236/2443.
Full textAbstract:
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$.
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 textAbstract:
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 degree i. We show that Colored (s,t)-Cut is W[2]-hard when parameterized by ξ3, but fixed-parameter tractable when parameterized by ξ2. Second, we consider parameters related to the coloring ℓ. We show fixed-parameter tractability for three parameters that are potentially smaller than the total number of colors |C| and provide a linear-size problem kernel for a parameter related to the number of edges with rare edge colors.
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 (July 24, 2020). http://dx.doi.org/10.37236/8239.
Full textAbstract:
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.
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 (October 20, 2008). http://dx.doi.org/10.37236/855.
Full textAbstract:
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$.
27
Wang, Guanghui, and Hao Li. "Heterochromatic Matchings in Edge-Colored Graphs." Electronic Journal of Combinatorics 15, no. 1 (November 14, 2008). http://dx.doi.org/10.37236/862.
Full textAbstract:
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.
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 (May 14, 2010). http://dx.doi.org/10.37236/475.
Full textAbstract:
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\rceil$ that fail to hold only for finitely many exceptions (for each odd $k$).
29
Jin, Zemin, and Xueliang Li. "Anti-Ramsey Numbers for Graphs with Independent Cycles." Electronic Journal of Combinatorics 16, no. 1 (July 9, 2009). http://dx.doi.org/10.37236/174.
Full textAbstract:
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.
30
Wang, Guanghui. "Rainbow Matchings in Properly Edge Colored Graphs." Electronic Journal of Combinatorics 18, no. 1 (August 5, 2011). http://dx.doi.org/10.37236/649.
Full textAbstract:
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$.
31
Grech, Mariusz, and Andrzej Kisielewicz. "All totally symmetric colored graphs." Discrete Mathematics & Theoretical Computer Science Vol. 15 no. 1, Graph Theory (March 22, 2013). http://dx.doi.org/10.46298/dmtcs.630.
Full textAbstract:
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.
32
Yuster, Raphael. "Rainbow $H$-factors." Electronic Journal of Combinatorics 13, no. 1 (February 15, 2006). http://dx.doi.org/10.37236/1039.
Full textAbstract:
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.
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 (September 8, 2017). http://dx.doi.org/10.37236/7049.
Full textAbstract:
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 monochromatic connected spanning subgraph. Our main result here is that for larger values of $k$ the situation is different, graphs of minimum degree $(1-\epsilon_k)n$ can replace complete graphs and still there is a monochromatic connected component of order at least ${n\over k-1}$, in fact $$\delta(G)\ge \left(1 - \frac{1}{1000(k-1)^9}\right)n$$ suffices.Our second result is an improvement of this bound for $k=3$. If the edges of $G$ with $\delta(G)\geq {9n\over 10}$ are $3$-colored, then there is a monochromatic component of order at least ${n\over 2}$. We conjecture that this can be improved to ${7n\over 9}$ and for general $k$ we conjecture the following: if $k\geq 3$ and $G$ is a graph of order $n$ such that $\delta(G)\geq \left( 1 - \frac{k-1}{k^2}\right)n$, then in any $k$-coloring of the edges of $G$ there is a monochromatic connected component of order at least ${n\over k-1}$.
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 (July 1, 2016). http://dx.doi.org/10.46298/dmtcs.2159.
Full textAbstract:
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 distinct colors. The monochromatic clique and multicolored cycle partition problems have important applications in the problems of network optimization arising in information science and operations research. We investigate the computational complexity of the problems of determining the minimum number of monochromatic cliques or multicolored cycles that, respectively, partition $V(G)$. We show that the minimum monochromatic clique partition problem is APX-hard on monochromatic-diamond-free graphs, and APX-complete on monochromatic-diamond-free graphs in which the size of a maximum monochromatic clique is bounded by a constant. We also show that the minimum multicolored cycle partition problem is NP-complete, even if the input graph $G$ is triangle-free. Moreover, for the weighted version of the minimum monochromatic clique partition problem on monochromatic-diamond-free graphs, we derive an approximation algorithm with (tight) approximation guarantee ln $|V(G)|+1$.
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 textAbstract:
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 edges inside each of the sets blue. The longest red path has 2|A|+1 vertices and the longest blue path has |B| vertices. The main result of this paper concerns the corresponding problem for countably infinite graphs. To measure the size of a monochromatic subgraph, we associate the vertices with positive integers and consider the lower and the upper density of the vertex set of a monochromatic subgraph. The upper density of a subset A of positive integers is the limit superior of |A∩{1,...,}|/n, and the lower density is the limit inferior. The following example shows that there need not exist a monochromatic path with positive upper density such that its vertices form an increasing sequence: an edge joining vertices i and j is colored red if ⌊log2i⌋≠⌊log2j⌋, and blue otherwise. In particular, the coloring yields blue cliques with 1, 2, 4, 8, etc., vertices mutually joined by red edges. Likewise, there are constructions of two-edge-colorings such that the lower density of every monochromatic path is zero. A result of Rado from the 1970's asserts that the vertices of any k-edge-colored countably infinite complete graph can be covered by k monochromatic paths. For a two-edge-colored complete graph on the positive integers, this implies the existence of a monochromatic path with upper density at least 1/2. In 1993, Erdős and Galvin raised the problem of determining the largest c such that every two-edge-coloring of the complete graph on the positive integers contains a monochromatic path with upper density at least c. The authors solve this 25-year-old problem by showing that c=(12+8–√)/17≈0.87226.
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 (June 19, 2014). http://dx.doi.org/10.46298/dmtcs.2093.
Full textAbstract:
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(G) and η(G), where rad(G) is the radius of G and η(G) is the smallest integer number such that every edge of G is contained in a cycle of length at most η(G). We also obtain constant bounds of the oriented diameter and the rainbow connection number for a (bipartite) graph G in terms of the minimum degree of G.
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 (September 3, 2012). http://dx.doi.org/10.46298/dmtcs.586.
Full textAbstract:
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., trails) in G(c) with endpoints in S. Further, if G(c) contains no PEC closed trails, we show that the problem of finding a PEC s-t trail visiting a given subset of vertices can be solved in polynomial time and prove that it becomes NP-complete if we are restricted to graphs with no PEC cycles. We also deal with graphs G(c) containing no (almost) PEC cycles or closed trails through s or t. We prove that finding 2 PEC s-t paths (resp., trails) with length at most L > 0 is NP-complete in the strong sense even for graphs with maximum degree equal to 3 and present an approximation algorithm for computing k vertex (resp., edge) disjoint PEC s-t paths (resp., trails) so that the maximum path (resp., trail) length is no more than k times the PEC path (resp., trail) length in an optimal solution. Further, we prove that finding 2 vertex disjoint s-t paths with exactly one PEC s-t path is NP-complete. This result is interesting since as proved in Abouelaoualim et. al.(2008), the determination of two or more vertex disjoint PEC s-t paths can be done in polynomial time. Finally, if G(c) is an arbitrary c-edge-colored graph with maximum vertex degree equal to four, we prove that finding two monochromatic vertex disjoint s-t paths with different colors is NP-complete. We also propose some related problems.
38
DeOrsey, Philip, Michael Ferrara, Nathan Graber, Stephen G. Hartke, Luke L. Nelsen, Eric Sullivan, Sogol Jahanbekam, Bernard Lidický, Derrick Stolee, and Jennifer White. "On the Strong Chromatic Index of Sparse Graphs." Electronic Journal of Combinatorics 25, no. 3 (July 27, 2018). http://dx.doi.org/10.37236/5390.
Full textAbstract:
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$ then $\chi'_{s,\ell}(G) \leq 5$, answering a question of Borodin and Ivanova [Precise upper bound for the strong edge chromatic number of sparse planar graphs, Discuss. Math. Graph Theory, 33(4), (2014) 759--770]. We further show that if $G$ is a subcubic planar graph and ${\rm girth}(G) \geq 30$, then $\chi_s'(G) \leq 5$, improving a bound from the same paper.Finally, if $G$ is a planar graph with maximum degree at most four and ${\rm girth}(G) \geq 28$, then $\chi'_s(G)N \leq 7$, improving a more general bound of Wang and Zhao from [Odd graphs and its applications to the strong edge coloring, Applied Mathematics and Computation, 325 (2018), 246-251] in this case.
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 textAbstract:
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 unchanged. This is the kind of "signed graph" found in knot theory. The natural generalization is to more colors and more general groups — or no group.Weighted graphs, in which the edge labels are the elements +1 and -1 of the integers or another additive domain. Weights behave like numbers, not signs; thus I regard work on weighted graphs as outside the scope of the bibliography — except (to some extent) when the author calls the weights "signs".Labelled graphs where the labels have no structure or properties but are called "signs" for any or no reason.
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 (July 16, 2024). http://dx.doi.org/10.1007/s40590-024-00645-0.
Full textAbstract:
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, with local restrictions given by an auxiliary graph, and we show sufficient conditions implying that every vertex in V(G) is contained in an H-cycle of length 3 (respectively 4). As a consequence, we obtain some well-known results in the theory of properly colored walks.
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 textAbstract:
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 constructed quite naturally. However, actually proving that they “capture polytopal symmetries” involves applying rather unexpected techniques from the intersection of convex geometry and spectral graph theory.
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 textAbstract:
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 containing more than $\frac{1}{4}n^2$ edges, give rise to a triangle with one edge from $G_1$ and two edges from $G_2$. The situation is however different for three colors. Fix $\tau=\frac{4-\sqrt{7}}{9}$ and split the $n$ vertices into three sets $A$, $B$ and $C$, such that $|B|=|C|=\lfloor\tau n\rfloor$ and $|A|=n-|B|-|C|$. The graph $G_1$ contains all edges inside $A$ and inside $B$, the graph $G_2$ contains all edges inside $A$ and inside $C$, and the graph $G_3$ contains all edges between $A$ and $B\cup C$ and inside $B\cup C$. It is easy to check that there is no triangle with one edge from $G_1$, one from $G_2$ and one from $G_3$; each of the graphs has about $\frac{1+\tau^2}{4}n^2=\frac{26-2\sqrt{7}}{81}n^2\approx 0.25566n^2$ edges. The main result of the article is that this construction is optimal: any three graphs $G_1$, $G_2$ and $G_3$ on the same set of $n$ vertices, each containing more than $\frac{1+\tau^2}{4}n^2$ edges, give rise to a triangle with one edge from each of the graphs $G_1$, $G_2$ and $G_3$. A computer-assisted proof of the same bound has been found by Culver, Lidický, Pfender and Volec.
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 (November 8, 2023). http://dx.doi.org/10.1186/s13015-023-00240-4.
Full textAbstract:
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 relative timing information of gene and species divergences is captured by three colored graphs that have the extant genes as vertices and the species in which the genes are found as vertex colors: the equal-divergence-time (EDT) graph, the later-divergence-time (LDT) graph and the prior-divergence-time (PDT) graph, which together form an edge partition of the complete graph. Results Here we give a complete characterization in terms of informative and forbidden triples that can be read off the three graphs and provide a polynomial time algorithm for constructing an evolutionary scenario that explains the graphs, provided such a scenario exists. While both LDT and PDT graphs are cographs, this is not true for the EDT graph in general. We show that every EDT graph is perfect. While the information about LDT and PDT graphs is necessary to recognize EDT graphs in polynomial-time for general scenarios, this extra information can be dropped in the HGT-free case. However, recognition of EDT graphs without knowledge of putative LDT and PDT graphs is NP-complete for general scenarios. In contrast, PDT graphs can be recognized in polynomial-time. We finally connect the EDT graph to the alternative definitions of orthology that have been proposed for scenarios with horizontal gene transfer. With one exception, the corresponding graphs are shown to be colored cographs.
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 (April 9, 2021). http://dx.doi.org/10.37236/9552.
Full textAbstract:
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.
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 (January 15, 2021). http://dx.doi.org/10.37236/8857.
Full textAbstract:
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 $(K_t, \mathcal{T}_k)$-co-critical graphs on $n$ vertices, where $\mathcal{T}_k$ denotes the family of all trees on $k$ vertices. Following Day [Saturated graphs of prescribed minimum degree, Combin. Probab. Comput. 26 (2017), 201–207], we apply graph bootstrap percolation on a not necessarily $K_t$-saturated graph to prove that for all $t\geqslant4 $ and $k\geqslant\max\{6, t\}$, there exists a constant $c(t, k)$ such that, for all $n \ge (t-1)(k-1)+1$, if $G$ is a $(K_t, \mathcal{T}_k)$-co-critical graph on $n$ vertices, then $$ e(G)\geqslant \left(\frac{4t-9}{2}+\frac{1}{2}\left\lceil \frac{k}{2} \right\rceil\right)n-c(t, k).$$ Furthermore, this linear bound is asymptotically best possible when $t\in\{4,5\}$ and $k\geqslant6$. The method we develop in this paper may shed some light on attacking Hanson and Toft's conjecture.
46
Li, Deqiong, and Yaoping Hou. "Hypergraph Coverings and their Zeta Functions." Electronic Journal of Combinatorics 25, no. 4 (December 21, 2018). http://dx.doi.org/10.37236/7764.
Full textAbstract:
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}$.
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 (January 29, 2021). http://dx.doi.org/10.37236/9066.
Full textAbstract:
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 independently colored with color $c_i$ with probability $\alpha_i$. We determine the threshold for the event $\mathrm{mcp}(G) = \{(m_1, \ldots, m_q) \in [0,n]^q : m_1 + \cdots + m_q = n\},$ answering a question posed by Frieze. We further extend our methods to find the threshold for the same event in a randomly colored random graph $G_{n,p}$.
48
Frieze, Alan, and Charalampos E. Tsourakakis. "Rainbow Connection of Sparse Random Graphs." Electronic Journal of Combinatorics 19, no. 4 (October 18, 2012). http://dx.doi.org/10.37236/2784.
Full textAbstract:
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 connectivity $rc(G)$ of $G=G(n,p)$ satisfies $rc(G) \sim \max\{Z_1,\text{diam}(G)\}$ with high probability (whp). Here $Z_1$ is the number of vertices in $G$ whose degree equals 1 and the diameter of $G$ is asymptotically equal to $\frac{\log n}{\log\log n}$ whp. Finally, we prove that the rainbow connectivity $rc(G)$ of the random $r$-regular graph $G=G(n,r)$ whp satisfies $rc(G) =O(\log^{2\theta_r}{n})$ where $\theta_r=\frac{\log (r-1)}{\log (r-2)}$ when $r\geq 4$ and $rc(G) =O(\log^4n)$ whp when $r=3$.
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 textAbstract:
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 vertices. The minimum k for which there exist a rainbow k−coloring of G is called the rainbow connection number of G, denoted by rc(G), the adjacent edges may be allowed to color with the same color. The graph G is strongly rainbow connected if there exists a rainbow u-v geodesic for every pair of vertices u and v in G.
50
Charpentier, Clément, Reza Naserasr, and Éric Sopena. "Homomorphisms of Sparse Signed Graphs." Electronic Journal of Combinatorics 27, no. 3 (July 10, 2020). http://dx.doi.org/10.37236/8478.
Full textAbstract:
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 preserves adjacencies, incidences, and signs of closed walks (i.e., the product of the sign of their edges). For $ij=00, 01, 10, 11$, let $g_{ij}(G,\sigma)$ be the length of a shortest nontrivial closed walk of $(G, \sigma)$ which is, positive and of even length for $ij=00$, positive and of odd length for $ij=01$, negative and of even length for $ij=10$, negative and of odd length for $ij=11$. For each $ij$, if there is no nontrivial closed walk of the corresponding type, we let $g_{ij}(G, \sigma)=\infty$. If $G$ is bipartite, then $g_{01}(G,\sigma)=g_{11}(G,\sigma)=\infty$. In this case, $g_{10}(G,\sigma)$ is certainly realized by a cycle of $G$, and it will be referred to as the \emph{unbalanced-girth} of $(G,\sigma)$.
It then follows that if $(G,\sigma)$ admits a homomorphism to $(H, \pi)$, then $g_{ij}(G, \sigma)\geq g_{ij}(H, \pi)$ for $ij \in \{00, 01,10,11\}$.
Studying the restriction of homomorphisms of signed graphs on sparse families, in this paper we first prove that for any given signed graph $(H, \pi)$, there exists a positive value of $\epsilon$ such that, if $G$ is a connected graph of maximum average degree less than $2+\epsilon$, and if $\sigma$ is a signature of $G$ such that $g_{ij}(G, \sigma)\geq g_{ij}(H, \pi)$ for all $ij \in \{00, 01,10,11\}$, then $(G, \sigma)$ admits a homomorphism to $(H, \pi)$.
For $(H, \pi)$ being the signed graph on $K_4$ with exactly one negative edge, we show that $\epsilon=\frac{4}{7}$ works and that this is the best possible value of $\epsilon$. For $(H, \pi)$ being the negative cycle of length $2g$, denoted $UC_{2g}$, we show that $\epsilon=\frac{1}{2g-1}$ works.
As a bipartite analogue of the Jaeger-Zhang conjecture, Naserasr, Sopena and Rollovà conjectured in [Homomorphisms of signed graphs, {\em J. Graph Theory} 79 (2015)] that every signed bipartite planar graph $(G,\sigma)$ satisfying $g_{ij}(G,\sigma)\geq 4g-2$ admits a homomorphism to $UC_{2g}$. We show that $4g-2$ cannot be strengthened, and, supporting the conjecture, we prove it for planar signed bipartite graphs $(G,\sigma)$ satisfying the weaker condition $g_{ij}(G,\sigma)\geq 8g-2$.
In the course of our work, we also provide a duality theorem to decide whether a 2-edge-colored graph admits a homomorphism to a certain class of 2-edge-colored signed graphs or not.