Acceder

Bibliografías temáticas / Edge-coloured graph / Artículos de revistas

Siga este enlace para ver otros tipos de publicaciones sobre el tema: Edge-coloured graph.

Artículos de revistas sobre el tema "Edge-coloured graph"

Autor: Grafiati

Publicado: 25 de mayo de 2024

Crea una cita precisa en los estilos APA, MLA, Chicago, Harvard y otros

Elija tipo de fuente:

Consulte los 50 mejores artículos de revistas para su investigación sobre el tema "Edge-coloured graph".

Junto a cada fuente en la lista de referencias hay un botón "Agregar a la bibliografía". Pulsa este botón, y generaremos automáticamente la referencia bibliográfica para la obra elegida en el estilo de cita que necesites: APA, MLA, Harvard, Vancouver, Chicago, etc.

También puede descargar el texto completo de la publicación académica en formato pdf y leer en línea su resumen siempre que esté disponible en los metadatos.

Explore artículos de revistas sobre una amplia variedad de disciplinas y organice su bibliografía correctamente.

1

COOPER, COLIN y ALAN FRIEZE. "Multi-Coloured Hamilton Cycles in Random Edge-Coloured Graphs". Combinatorics, Probability and Computing 11, n.º 2 (marzo de 2002): 129–33. http://dx.doi.org/10.1017/s0963548301005004.

Texto completo

Resumen

We define a space of random edge-coloured graphs [Gscr ]n,m,κ which correspond naturally to edge κ-colourings of Gn,m. We show that there exist constants K0, K1 [les ] 21 such that, provided m [ges ] K0n log n and κ [ges ] K1n, then a random edge-coloured graph contains a multi-coloured Hamilton cycle with probability tending to 1 as the number of vertices n tends to infinity.

Los estilos APA, Harvard, Vancouver, ISO, etc.

2

KOSTOCHKA, ALEXANDR y MATTHEW YANCEY. "Large Rainbow Matchings in Edge-Coloured Graphs". Combinatorics, Probability and Computing 21, n.º 1-2 (2 de febrero de 2012): 255–63. http://dx.doi.org/10.1017/s0963548311000605.

Texto completo

Resumen

Arainbow subgraphof an edge-coloured graph is a subgraph whose edges have distinct colours. Thecolour degreeof a vertexvis the number of different colours on edges incident withv. Wang and Li conjectured that fork≥ 4, every edge-coloured graph with minimum colour degreekcontains a rainbow matching of size at least ⌈k/2⌉. A properly edge-colouredK4has no such matching, which motivates the restrictionk≥ 4, but Li and Xu proved the conjecture for all other properly coloured complete graphs. LeSaulnier, Stocker, Wenger and West showed that a rainbow matching of size ⌊k/2⌋ is guaranteed to exist, and they proved several sufficient conditions for a matching of size ⌈k/2⌉. We prove the conjecture in full.

Los estilos APA, Harvard, Vancouver, ISO, etc.

3

BENEVIDES, F. S., T. ŁUCZAK, A. SCOTT, J. SKOKAN y M. WHITE. "Monochromatic Cycles in 2-Coloured Graphs". Combinatorics, Probability and Computing 21, n.º 1-2 (marzo de 2012): 57–87. http://dx.doi.org/10.1017/s0963548312000090.

Texto completo

Resumen

Li, Nikiforov and Schelp [13] conjectured that any 2-edge coloured graph G with order n and minimum degree δ(G) > 3n/4 contains a monochromatic cycle of length ℓ, for all ℓ ∈ [4, ⌈n/2⌉]. We prove this conjecture for sufficiently large n and also find all 2-edge coloured graphs with δ(G)=3n/4 that do not contain all such cycles. Finally, we show that, for all δ>0 and n>n0(δ), if G is a 2-edge coloured graph of order n with δ(G) ≥ 3n/4, then one colour class either contains a monochromatic cycle of length at least (2/3+δ/2)n, or contains monochromatic cycles of all lengths ℓ ∈ [3, (2/3−δ)n].

Los estilos APA, Harvard, Vancouver, ISO, etc.

4

DIAO, Y. y G. HETYEI. "Relative Tutte Polynomials of Tensor Products of Coloured Graphs". Combinatorics, Probability and Computing 22, n.º 6 (4 de septiembre de 2013): 801–28. http://dx.doi.org/10.1017/s0963548313000370.

Texto completo

Resumen

The tensor product (G1,G2) of a graph G1 and a pointed graph G2 (containing one distinguished edge) is obtained by identifying each edge of G1 with the distinguished edge of a separate copy of G2, and then removing the identified edges. A formula to compute the Tutte polynomial of a tensor product of graphs was originally given by Brylawski. This formula was recently generalized to coloured graphs and the generalized Tutte polynomial introduced by Bollobás and Riordan. In this paper we generalize the coloured tensor product formula to relative Tutte polynomials of relative graphs, containing zero edges to which the usual deletion/contraction rules do not apply. As we have shown in a recent paper, relative Tutte polynomials may be used to compute the Jones polynomial of a virtual knot.

Los estilos APA, Harvard, Vancouver, ISO, etc.

5

KITTIPASSORN, TEERADEJ y BHARGAV P. NARAYANAN. "A Canonical Ramsey Theorem for Exactly m-Coloured Complete Subgraphs". Combinatorics, Probability and Computing 23, n.º 1 (18 de octubre de 2013): 102–15. http://dx.doi.org/10.1017/s0963548313000503.

Texto completo

Resumen

Given an edge colouring of a graph with a set of m colours, we say that the graph is exactly m-coloured if each of the colours is used. We consider edge colourings of the complete graph on $\mathbb{N}$ with infinitely many colours and show that either one can find an exactly m-coloured complete subgraph for every natural number m or there exists an infinite subset X ⊂ $\mathbb{N}$ coloured in one of two canonical ways: either the colouring is injective on X or there exists a distinguished vertex v in X such that X\{v} is 1-coloured and each edge between v and X\{v} has a distinct colour (all different to the colour used on X\{v}). This answers a question posed by Stacey and Weidl in 1999. The techniques that we develop also enable us to resolve some further questions about finding exactly m-coloured complete subgraphs in colourings with finitely many colours.

Los estilos APA, Harvard, Vancouver, ISO, etc.

6

Brewster, Richard C., Florent Foucaud, Pavol Hell y Reza Naserasr. "The complexity of signed graph and edge-coloured graph homomorphisms". Discrete Mathematics 340, n.º 2 (febrero de 2017): 223–35. http://dx.doi.org/10.1016/j.disc.2016.08.005.

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

7

Pham Ngoc, Diep. "A new condition for a graph having conflict free connection number 2". Journal of Science Natural Science 66, n.º 1 (marzo de 2021): 25–29. http://dx.doi.org/10.18173/2354-1059.2021-0003.

Texto completo

Resumen

A path in an edge-coloured graph is called conflict-free if there is a colour used on exactly one of its edges. An edge-coloured graph is said to be conflict-free connected if any two distinct vertices of the graph are connected by a conflict-free path. The conflict-free connection number, denoted by cf c(G), is the smallest number of colours needed in order to make G conflict-free connected. In this paper, we give a new condition to show that a connected non-complete graph G having cf c(G) = 2. This is an extension of a result by Chang et al. [1].

Los estilos APA, Harvard, Vancouver, ISO, etc.

8

Fujita, Shinya, Ruonan Li y Guanghui Wang. "Decomposing edge-coloured graphs under colour degree constraints". Combinatorics, Probability and Computing 28, n.º 5 (1 de marzo de 2019): 755–67. http://dx.doi.org/10.1017/s0963548319000014.

Texto completo

Resumen

AbstractFor an edge-coloured graph G, the minimum colour degree of G means the minimum number of colours on edges which are incident to each vertex of G. We prove that if G is an edge-coloured graph with minimum colour degree at least 5, then V(G) can be partitioned into two parts such that each part induces a subgraph with minimum colour degree at least 2. We show this theorem by proving amuch stronger form. Moreover, we point out an important relationship between our theorem and Bermond and Thomassen’s conjecture in digraphs.

Los estilos APA, Harvard, Vancouver, ISO, etc.

9

Piejko, Krzysztof y Iwona Włoch. "Onk-Distance Pell Numbers in 3-Edge-Coloured Graphs". Journal of Applied Mathematics 2014 (2014): 1–6. http://dx.doi.org/10.1155/2014/428020.

Texto completo

Resumen

We define in this paper new distance generalizations of the Pell numbers and the companion Pell numbers. We give a graph interpretation of these numbers with respect to a special 3-edge colouring of the graph.

Los estilos APA, Harvard, Vancouver, ISO, etc.

10

MARCINISZYN, MARTIN, RETO SPÖHEL y ANGELIKA STEGER. "Upper Bounds for Online Ramsey Games in Random Graphs". Combinatorics, Probability and Computing 18, n.º 1-2 (marzo de 2009): 259–70. http://dx.doi.org/10.1017/s0963548308009620.

Texto completo

Resumen

Consider the following one-player game. Starting with the empty graph onnvertices, in every step a new edge is drawn uniformly at random and inserted into the current graph. This edge has to be coloured immediately with one ofravailable colours. The player's goal is to avoid creating a monochromatic copy of some fixed graphFfor as long as possible. We prove an upper bound on the typical duration of this game ifFis from a large class of graphs including cliques and cycles of arbitrary size. Together with lower bounds published elsewhere, explicit threshold functions follow.

Los estilos APA, Harvard, Vancouver, ISO, etc.

11

Rahayuningtyas, Handrini, Abdussakir Abdussakir y Achmad Nashichuddin. "Bilangan Kromatik Grap Commuting dan Non Commuting Grup Dihedral". CAUCHY 4, n.º 1 (15 de noviembre de 2015): 16. http://dx.doi.org/10.18860/ca.v4i1.3169.

Texto completo

Resumen

Commuting graph is a graph that has a set of points X and two different vertices to be connected directly if each commutative in G. Let G non abelian group and Z(G) is a center of G. Noncommuting graph is a graph which the the vertex is a set of G\Z(G) and two vertices x and y are adjacent if and only if xy≠yx. The vertex colouring of G is giving k colour at the vertex, two vertices that are adjacent not given the same colour. Edge colouring of G is two edges that have common vertex are coloured with different colour. The smallest number k so that a graph can be coloured by assigning k colours to the vertex and edge called chromatic number. In this article, it is available the general formula of chromatic number of commuting and noncommuting graph of dihedral group

Los estilos APA, Harvard, Vancouver, ISO, etc.

12

Ferri, Massimo. "Colour Switching and Homeomorphism of Manifolds". Canadian Journal of Mathematics 39, n.º 1 (1 de febrero de 1987): 8–32. http://dx.doi.org/10.4153/cjm-1987-002-5.

Texto completo

Resumen

Throughout this paper, we work in the PL and pseudosimplicial categories, for which we refer to [17] and [10] respectively. For the graph theory involved see [9].An h-coloured graph (Γ, γ) is a multigraph Γ = (V(Γ), E(Γ)) regular of degree h, endowed with an edge-coloration γ by h colours. If is the colour set, for each we setFor each set . For n ∊ Z, n ≧ 1, setΔn will be mostly used to denote the colour set for an (n + 1)-coloured graph.

Los estilos APA, Harvard, Vancouver, ISO, etc.

13

LETZTER, SHOHAM. "Path Ramsey Number for Random Graphs". Combinatorics, Probability and Computing 25, n.º 4 (7 de diciembre de 2015): 612–22. http://dx.doi.org/10.1017/s0963548315000279.

Texto completo

Resumen

Answering a question raised by Dudek and Prałat, we show that if pn → ∞, w.h.p., whenever G = G(n, p) is 2-edge-coloured there is a monochromatic path of length (2/3 + o(1))n. This result is optimal in the sense that 2/3 cannot be replaced by a larger constant.As part of the proof we obtain the following result. Given a graph G on n vertices with at least $(1-\varepsilon)\binom{n}{2}$ edges, whenever G is 2-edge-coloured, there is a monochromatic path of length at least $(2/3 - 110\sqrt{\varepsilon})n$. This is an extension of the classical result by Gerencsér and Gyárfás which says that whenever Kn is 2-coloured there is a monochromatic path of length at least 2n/3.

Los estilos APA, Harvard, Vancouver, ISO, etc.

14

Nguyen Thi Thuy, Anh y Duyen Le Thi. "A NOTE ON GENERALIZED RAINBOW CONNECTION OF CONNECTED GRAPHS AND THEIR NUMBER OF EDGES". Journal of Science Natural Science 66, n.º 3 (octubre de 2021): 3–7. http://dx.doi.org/10.18173/2354-1059.2021-0041.

Texto completo

Resumen

Let l ≥ 1, k ≥ 1 be two integers. Given an edge-coloured connected graph G. A path P in the graph G is called l-rainbow path if each subpath of length at most l + 1 is rainbow. The graph G is called (k, l)-rainbow connected if any two vertices in G are connected by at least k pairwise internally vertex-disjoint l-rainbow paths. The smallest number of colours needed in order to make G (k, l)-rainbow connected is called the (k, l)-rainbow connection number of G and denoted by rck,l(G). In this paper, we first focus to improve the upper bound of the (1, l)-rainbow connection number depending on the size of connected graphs. Using this result, we characterize all connected graphs having the large (1, 2)-rainbow connection number. Moreover, we also determine the (1, l)-rainbow connection number in a connected graph G containing a sequence of cut-edges.

Los estilos APA, Harvard, Vancouver, ISO, etc.

15

Král’, Daniel, Edita Máčajov´, Attila Pór y Jean-Sébastien Sereni. "Characterisation Results for Steiner Triple Systems and Their Application to Edge-Colourings of Cubic Graphs". Canadian Journal of Mathematics 62, n.º 2 (1 de abril de 2010): 355–81. http://dx.doi.org/10.4153/cjm-2010-021-9.

Texto completo

Resumen

AbstractIt is known that a Steiner triple system is projective if and only if it does not contain the four-triple configuration C14. We find three configurations such that a Steiner triple system is affine if and only if it does not contain one of these configurations. Similarly, we characterise Hall triple systems using two forbidden configurations.Our characterisations have several interesting corollaries in the area of edge-colourings of graphs. A cubic graph G is S-edge-colourable for a Steiner triple system S if its edges can be coloured with points of S in such a way that the points assigned to three edges sharing a vertex form a triple in S. Among others, we show that all cubic graphs are S-edge-colourable for every non-projective nonaffine point-transitive Steiner triple system S.

Los estilos APA, Harvard, Vancouver, ISO, etc.

16

Brunetti, Maurizio y Alma D'Aniello. "On a graph connecting hyperbinary expansions". Publications de l'Institut Math?matique (Belgrade) 105, n.º 119 (2019): 25–38. http://dx.doi.org/10.2298/pim1919025b.

Texto completo

Resumen

A hyperbinary expansion of n is a representation of n as sum of powers of 2, each power being used at most twice. We study some properties of a suitable edge-coloured and vertex-weighted oriented graph A(n) whose nodes are precisely the several hyperbinary representations of n. Such graph suggests a method to measure the non-binarity of a hyperbinary expansion. We discuss how it is related to (p,q)-hyperbinary expansions. Finally, we identify those integers m\in\N such that the fundamental group of A(m) is Abelian.

Los estilos APA, Harvard, Vancouver, ISO, etc.

17

MARCINISZYN, MARTIN, RETO SPÖHEL y ANGELIKA STEGER. "Online Ramsey Games in Random Graphs". Combinatorics, Probability and Computing 18, n.º 1-2 (marzo de 2009): 271–300. http://dx.doi.org/10.1017/s0963548308009632.

Texto completo

Resumen

Consider the following one-player game. Starting with the empty graph onnvertices, in every step a new edge is drawn uniformly at random and inserted into the current graph. This edge has to be coloured immediately with one ofravailable colours. The player's goal is to avoid creating a monochromatic copy of some fixed graphFfor as long as possible. We prove a lower bound ofnβ(F,r)on the typical duration of this game, where β(F,r) is a function that is strictly increasing inrand satisfies limr→∞β(F,r) = 2 − 1/m2(F), wheren2−1/m2(F)is the threshold of the corresponding offline colouring problem.

Los estilos APA, Harvard, Vancouver, ISO, etc.

18

Saad, Rachid. "Finding a Longest Alternating Cycle in a 2-edge-coloured Complete Graph is in RP". Combinatorics, Probability and Computing 5, n.º 3 (septiembre de 1996): 297–306. http://dx.doi.org/10.1017/s0963548300002054.

Texto completo

Resumen

Jackson [10] gave a polynomial sufficient condition for a bipartite tournament to contain a cycle of a given length. The question arises as to whether deciding on the maximum length of a cycle in a bipartite tournament is polynomial. The problem was considered by Manoussakis [12] in the slightly more general setting of 2-edge coloured complete graphs: is it polynomial to find a longest alternating cycle in such coloured graphs? In this paper, strong evidence is given that such an algorithm exists. In fact, using a reduction to the well known exact matching problem, we prove that the problem is random polynomial.

Los estilos APA, Harvard, Vancouver, ISO, etc.

19

CASALI, MARIA RITA. "FROM FRAMED LINKS TO CRYSTALLIZATIONS OF BOUNDED 4-MANIFOLDS". Journal of Knot Theory and Its Ramifications 09, n.º 04 (junio de 2000): 443–58. http://dx.doi.org/10.1142/s0218216500000220.

Texto completo

Resumen

It is well-known that every 3-manifold M3 may be represented by a framed link (L,c), which indicates the Dehn-surgery from [Formula: see text] to M3 = M3(L,c); moreover, M3 is the boundary of a PL 4-manifold M4 = M4(L, c), which is obtained from [Formula: see text] by adding 2-handles along the framed link (L, c). In this paper we study the relationships between the above representations and the representation theory of general PL-manifolds by edge-coloured graphs: in particular, we describe how to construct a 5-coloured graph representing M4=M4(L,c), directly from a planar diagram of (L,c). As a consequence, relations between the combinatorial properties of the link L and both the Heegaard genus of M3=M3(L,c) and the regular genus of M4=M4(L,c) are obtained.

Los estilos APA, Harvard, Vancouver, ISO, etc.

20

Dobrinen, Natasha. "The Ramsey theory of the universal homogeneous triangle-free graph". Journal of Mathematical Logic 20, n.º 02 (28 de enero de 2020): 2050012. http://dx.doi.org/10.1142/s0219061320500129.

Texto completo

Resumen

The universal homogeneous triangle-free graph, constructed by Henson [A family of countable homogeneous graphs, Pacific J. Math. 38(1) (1971) 69–83] and denoted [Formula: see text], is the triangle-free analogue of the Rado graph. While the Ramsey theory of the Rado graph has been completely established, beginning with Erdős–Hajnal–Posá [Strong embeddings of graphs into coloured graphs, in Infinite and Finite Sets. Vol.[Formula: see text] , eds. A. Hajnal, R. Rado and V. Sós, Colloquia Mathematica Societatis János Bolyai, Vol. 10 (North-Holland, 1973), pp. 585–595] and culminating in work of Sauer [Coloring subgraphs of the Rado graph, Combinatorica 26(2) (2006) 231–253] and Laflamme–Sauer–Vuksanovic [Canonical partitions of universal structures, Combinatorica 26(2) (2006) 183–205], the Ramsey theory of [Formula: see text] had only progressed to bounds for vertex colorings [P. Komjáth and V. Rödl, Coloring of universal graphs, Graphs Combin. 2(1) (1986) 55–60] and edge colorings [N. Sauer, Edge partitions of the countable triangle free homogenous graph, Discrete Math. 185(1–3) (1998) 137–181]. This was due to a lack of broadscale techniques. We solve this problem in general: For each finite triangle-free graph [Formula: see text], there is a finite number [Formula: see text] such that for any coloring of all copies of [Formula: see text] in [Formula: see text] into finitely many colors, there is a subgraph of [Formula: see text] which is again universal homogeneous triangle-free in which the coloring takes no more than [Formula: see text] colors. This is the first such result for a homogeneous structure omitting copies of some nontrivial finite structure. The proof entails developments of new broadscale techniques, including a flexible method for constructing trees which code [Formula: see text] and the development of their Ramsey theory.

Los estilos APA, Harvard, Vancouver, ISO, etc.

21

ALLEN, PETER. "Covering Two-Edge-Coloured Complete Graphs with Two Disjoint Monochromatic Cycles". Combinatorics, Probability and Computing 17, n.º 4 (julio de 2008): 471–86. http://dx.doi.org/10.1017/s0963548308009164.

Texto completo

Resumen

In 1998 Łuczak Rödl and Szemerédi [7] proved, by means of the Regularity Lemma, that there exists n0 such that, for any n ≥ n0 and two-edge-colouring of Kn, there exists a pair of vertex-disjoint monochromatic cycles of opposite colours covering the vertices of Kn. In this paper we make use of an alternative method of finding useful structure in a graph, leading to a proof of the same result with a much smaller value of n0. The proof gives a polynomial-time algorithm for finding the two cycles.

Los estilos APA, Harvard, Vancouver, ISO, etc.

22

BOLLOBÁS, BÉLA y OLIVER RIORDAN. "A Tutte Polynomial for Coloured Graphs". Combinatorics, Probability and Computing 8, n.º 1-2 (enero de 1999): 45–93. http://dx.doi.org/10.1017/s0963548398003447.

Texto completo

Resumen

We define a polynomial W on graphs with colours on the edges, by generalizing the spanning tree expansion of the Tutte polynomial as far as possible: we give necessary and sufficient conditions on the edge weights for this expansion not to depend on the order used. We give a contraction-deletion formula for W analogous to that for the Tutte polynomial, and show that any coloured graph invariant satisfying such a formula can be obtained from W. In particular, we show that generalizations of the Tutte polynomial obtained from its rank generating function formulation, or from a random cluster model, can be obtained from W. Finally, we find the most general conditions under which W gives rise to a link invariant, and give as examples the one-variable Jones polynomial, and an invariant taking values in ℤ/22ℤ.

Los estilos APA, Harvard, Vancouver, ISO, etc.

23

Wouters, Jurriaan, Aris Giotis, Ross Kang, Dirk Schuricht y Lars Fritz. "Lower bounds for Ramsey numbers as a statistical physics problem". Journal of Statistical Mechanics: Theory and Experiment 2022, n.º 3 (1 de marzo de 2022): 033211. http://dx.doi.org/10.1088/1742-5468/ac5cb3.

Texto completo

Resumen

Abstract Ramsey’s theorem, concerning the guarantee of certain monochromatic patterns in large enough edge-coloured complete graphs, is a fundamental result in combinatorial mathematics. In this work, we highlight the connection between this abstract setting and a statistical physics problem. Specifically, we design a classical Hamiltonian that favours configurations in a way to establish lower bounds on Ramsey numbers. As a proof of principle we then use Monte Carlo methods to obtain such lower bounds, finding rough agreement with known literature values in a few cases we investigated. We discuss numerical limitations of our approach and indicate a path towards the treatment of larger graph sizes.

Los estilos APA, Harvard, Vancouver, ISO, etc.

24

Gao, Pu, Reshma Ramadurai, Ian M. Wanless y Nick Wormald. "Full rainbow matchings in graphs and hypergraphs". Combinatorics, Probability and Computing 30, n.º 5 (20 de enero de 2021): 762–80. http://dx.doi.org/10.1017/s0963548320000620.

Texto completo

Resumen

AbstractLet G be a simple graph that is properly edge-coloured with m colours and let \[\mathcal{M} = \{ {M_1},...,{M_m}\} \] be the set of m matchings induced by the colours in G. Suppose that \[m \leqslant n - {n^c}\], where \[c > 9/10\], and every matching in \[\mathcal{M}\] has size n. Then G contains a full rainbow matching, i.e. a matching that contains exactly one edge from Mi for each \[1 \leqslant i \leqslant m\]. This answers an open problem of Pokrovskiy and gives an affirmative answer to a generalization of a special case of a conjecture of Aharoni and Berger. Related results are also found for multigraphs with edges of bounded multiplicity, and for hypergraphs.Finally, we provide counterexamples to several conjectures on full rainbow matchings made by Aharoni and Berger.

Los estilos APA, Harvard, Vancouver, ISO, etc.

25

ALAPPATTU, JOMY y JIM PITMAN. "Coloured Loop-Erased Random Walk on the Complete Graph". Combinatorics, Probability and Computing 17, n.º 6 (noviembre de 2008): 727–40. http://dx.doi.org/10.1017/s0963548308009115.

Texto completo

Resumen

Starting from a sequence regarded as a walk through some set of values, we consider the associated loop-erased walk as a sequence of directed edges, with an edge from i to j if the loop-erased walk makes a step from i to j. We introduce a colouring of these edges by painting edges with a fixed colour as long as the walk does not loop back on itself, then switching to a new colour whenever a loop is erased, with each new colour distinct from all previous colours. The pattern of colours along the edges of the loop-erased walk then displays stretches of consecutive steps of the walk left untouched by the loop-erasure process. Assuming that the underlying sequence generating the loop-erased walk is a sequence of independent random variables, each uniform on [N] := {1, 2, . . ., N}, we condition the walk to start at N and stop the walk when it first reaches the subset [k], for some 1 ≤ k ≤ N − 1. We relate the distribution of the random length of this loop-erased walk to the distribution of the length of the first loop of the walk, via Cayley's enumerations of trees, and via Wilson's algorithm. For fixed N and k, and i = 1, 2, . . ., let Bi denote the events that the loop-erased walk from N to [k] has i + 1 or more edges, and the ith and (i + 1)th of these edges are coloured differently. We show that, given that the loop-erased random walk has j edges for some 1 ≤ j ≤ N − k, the events Bi for 1 ≤ i ≤ j − 1 are independent, with the probability of Bi equal to 1/(k + i + 1). This determines the distribution of the sequence of random lengths of differently coloured segments of the loop-erased walk, and yields asymptotic descriptions of these random lengths as N → ∞.

Los estilos APA, Harvard, Vancouver, ISO, etc.

26

BOUSQUET, NICOLAS, LOUIS ESPERET, ARARAT HARUTYUNYAN y RÉMI DE JOANNIS DE VERCLOS. "Exact Distance Colouring in Trees". Combinatorics, Probability and Computing 28, n.º 2 (24 de julio de 2018): 177–86. http://dx.doi.org/10.1017/s0963548318000378.

Texto completo

Resumen

For an integer q ⩾ 2 and an even integer d, consider the graph obtained from a large complete q-ary tree by connecting with an edge any two vertices at distance exactly d in the tree. This graph has clique number q + 1, and the purpose of this short note is to prove that its chromatic number is Θ((d log q)/log d). It was not known that the chromatic number of this graph grows with d. As a simple corollary of our result, we give a negative answer to a problem of van den Heuvel and Naserasr, asking whether there is a constant C such that for any odd integer d, any planar graph can be coloured with at most C colours such that any pair of vertices at distance exactly d have distinct colours. Finally, we study interval colouring of trees (where vertices at distance at least d and at most cd, for some real c > 1, must be assigned distinct colours), giving a sharp upper bound in the case of bounded degree trees.

Los estilos APA, Harvard, Vancouver, ISO, etc.

27

PACH, JÁNOS y GÁBOR TARDOS. "Conflict-Free Colourings of Graphs and Hypergraphs". Combinatorics, Probability and Computing 18, n.º 5 (septiembre de 2009): 819–34. http://dx.doi.org/10.1017/s0963548309990290.

Texto completo

Resumen

A colouring of the vertices of a hypergraphHis calledconflict-freeif each hyperedgeEofHcontains a vertex of ‘unique’ colour that does not get repeated inE. The smallest number of colours required for such a colouring is called theconflict-free chromatic numberofH, and is denoted by χCF(H). This parameter was first introduced by Even, Lotker, Ron and Smorodinsky (FOCS2002) in ageometricsetting, in connection with frequency assignment problems for cellular networks. Here we analyse this notion for general hypergraphs. It is shown that$\chi_{\rm CF}(H)\leq 1/2+\sqrt{2m+1/4}$, for every hypergraph withmedges, and that this bound is tight. Better bounds of the order ofm1/tlogmare proved under the assumption that the size of every edge ofHis at least 2t− 1, for somet≥ 3. Using Lovász's Local Lemma, the same result holds for hypergraphs in which the size of every edge is at least 2t− 1 and every edge intersects at mostmothers. We give efficient polynomial-time algorithms to obtain such colourings.Our machinery can also be applied to the hypergraphs induced by the neighbourhoods of the vertices of a graph. It turns out that in this case we need far fewer colours. For example, it is shown that the vertices of any graphGwith maximum degree Δ can be coloured with log2+εΔ colours, so that the neighbourhood of every vertex contains a point of ‘unique’ colour. We give an efficient deterministic algorithm to find such a colouring, based on a randomized algorithmic version of the Lovász Local Lemma, suggested by Beck, Molloy and Reed. To achieve this, we need to (1) correct a small error in the Molloy–Reed approach, (2) restate and re-prove their result in adeterministicform.

Los estilos APA, Harvard, Vancouver, ISO, etc.

28

Brewster, Richard C. y Timothy Graves. "Edge-switching homomorphisms of edge-coloured graphs". Discrete Mathematics 309, n.º 18 (septiembre de 2009): 5540–46. http://dx.doi.org/10.1016/j.disc.2008.03.021.

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

29

Lo, Allan. "Long properly coloured cycles in edge-coloured graphs". Journal of Graph Theory 90, n.º 3 (2 de noviembre de 2018): 416–42. http://dx.doi.org/10.1002/jgt.22405.

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

30

Bang-Jensen, J., G. Gutin y A. Yeo. "Properly coloured Hamiltonian paths in edge-coloured complete graphs". Discrete Applied Mathematics 82, n.º 1-3 (marzo de 1998): 247–50. http://dx.doi.org/10.1016/s0166-218x(97)00062-0.

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

31

Lo, Allan. "Properly coloured Hamiltonian cycles in edge-coloured complete graphs". Combinatorica 36, n.º 4 (24 de junio de 2015): 471–92. http://dx.doi.org/10.1007/s00493-015-3067-1.

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

32

Tsukui, Yasuyuki. "Transformations of edge-coloured cubic graphs". Discrete Mathematics 184, n.º 1-3 (abril de 1998): 183–94. http://dx.doi.org/10.1016/s0012-365x(97)00088-5.

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

33

Axenovich, Maria, Tao Jiang y Z. Tuza. "Local Anti-Ramsey Numbers of Graphs". Combinatorics, Probability and Computing 12, n.º 5-6 (noviembre de 2003): 495–511. http://dx.doi.org/10.1017/s0963548303005868.

Texto completo

Resumen

A subgraph H in an edge-colouring is properly coloured if incident edges of H are assigned different colours, and H is rainbow if no two edges of H are assigned the same colour. We study properly coloured subgraphs and rainbow subgraphs forced in edge-colourings of complete graphs in which each vertex is incident to a large number of colours.

Los estilos APA, Harvard, Vancouver, ISO, etc.

34

Kanté, Mamadou Moustapha y Michael Rao. "The Rank-Width of Edge-Coloured Graphs". Theory of Computing Systems 52, n.º 4 (14 de abril de 2012): 599–644. http://dx.doi.org/10.1007/s00224-012-9399-y.

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

35

Casali, Maria Rita y Luigi Grasselli. "Representing branched coverings by Edge-Coloured Graphs". Topology and its Applications 33, n.º 2 (octubre de 1989): 197–207. http://dx.doi.org/10.1016/s0166-8641(89)80008-2.

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

36

Idzik, Adam, Jan Komar y Marcin Malawski. "Edge-coloured complete graphs: Connectedness of some subgraphs". Discrete Mathematics 66, n.º 1-2 (agosto de 1987): 119–25. http://dx.doi.org/10.1016/0012-365x(87)90124-5.

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

37

Pokrovskiy, Alexey. "Partitioning edge-coloured complete graphs into monochromatic cycles". Electronic Notes in Discrete Mathematics 43 (septiembre de 2013): 311–17. http://dx.doi.org/10.1016/j.endm.2013.07.049.

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

38

Hilton, A. J. W. "Alternating Hamiltonian circuits in edge-coloured bipartite graphs". Discrete Applied Mathematics 35, n.º 3 (marzo de 1992): 271–73. http://dx.doi.org/10.1016/0166-218x(92)90249-a.

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

39

Idzik, Adam. "Estimation of cut-vertices in edge-coloured complete graphs". Discussiones Mathematicae Graph Theory 25, n.º 1-2 (2005): 217. http://dx.doi.org/10.7151/dmgt.1274.

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

40

Idzik, Adam y Zsolt Tuza. "Heredity properties of connectedness in edge-coloured complete graphs". Discrete Mathematics 235, n.º 1-3 (mayo de 2001): 301–6. http://dx.doi.org/10.1016/s0012-365x(00)00282-x.

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

41

Galeana-Sánchez, H. "Kernels in edge-coloured orientations of nearly complete graphs". Discrete Mathematics 308, n.º 20 (octubre de 2008): 4599–607. http://dx.doi.org/10.1016/j.disc.2007.08.079.

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

42

Yeo, Anders. "A Note on Alternating Cycles in Edge-Coloured Graphs". Journal of Combinatorial Theory, Series B 69, n.º 2 (marzo de 1997): 222–25. http://dx.doi.org/10.1006/jctb.1997.1728.

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

43

Pokrovskiy, Alexey y Benny Sudakov. "Edge-disjoint rainbow trees in properly coloured complete graphs". Electronic Notes in Discrete Mathematics 61 (agosto de 2017): 995–1001. http://dx.doi.org/10.1016/j.endm.2017.07.064.

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

44

Dugdale, J. K. y A. J. W. Hilton. "Amalgamated Factorizations of Complete Graphs". Combinatorics, Probability and Computing 3, n.º 2 (junio de 1994): 215–32. http://dx.doi.org/10.1017/s0963548300001127.

Texto completo

Resumen

We give some sufficient conditions for an (S, U)-outline T-factorization of Kn to be an (S, U)-amalgamated T-factorization of Kn. We then apply these to give various necessary and sufficient conditions for edge coloured graphs G to have recoverable embeddings in T-factorized Kn's.

Los estilos APA, Harvard, Vancouver, ISO, etc.

45

Lo, Allan y Ta Sheng Tan. "A Note on Large Rainbow Matchings in Edge-coloured Graphs". Graphs and Combinatorics 30, n.º 2 (12 de diciembre de 2012): 389–93. http://dx.doi.org/10.1007/s00373-012-1271-y.

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

46

Bürger, Carl y Max Pitz. "Partitioning edge-coloured infinite complete bipartite graphs into monochromatic paths". Israel Journal of Mathematics 238, n.º 1 (5 de junio de 2020): 479–500. http://dx.doi.org/10.1007/s11856-020-2030-z.

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

47

Lang, Richard, Oliver Schaudt y Maya Stein. "Partitioning 3-edge-coloured complete bipartite graphs into monochromatic cycles". Electronic Notes in Discrete Mathematics 49 (noviembre de 2015): 787–94. http://dx.doi.org/10.1016/j.endm.2015.06.106.

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

48

Pokrovskiy, Alexey. "Partitioning edge-coloured complete graphs into monochromatic cycles and paths". Journal of Combinatorial Theory, Series B 106 (mayo de 2014): 70–97. http://dx.doi.org/10.1016/j.jctb.2014.01.003.

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

49

Pokrovskiy, Alexey y Benny Sudakov. "Linearly many rainbow trees in properly edge-coloured complete graphs". Journal of Combinatorial Theory, Series B 132 (septiembre de 2018): 134–56. http://dx.doi.org/10.1016/j.jctb.2018.03.005.

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

50

Casali, Maria Rita. "The Average Edge Order of 3-Manifold Coloured Triangulations". Canadian Mathematical Bulletin 37, n.º 2 (1 de junio de 1994): 154–61. http://dx.doi.org/10.4153/cmb-1994-022-x.

Texto completo

Resumen

AbstractIf K is a triangulation of a closed 3-manifold M with E0(K) edges and F0(K) triangles, then the average edge order of K is defined to beIn [8], the relations between this quantity and the topology of M are investigated, especially in the case of μ0(K) being small (where the study relies on Oda's classification of triangulations of 𝕊2 up to eight vertices—see [9]). In the present paper, the attention is fixed upon the average edge order of coloured triangulations; surprisingly enough, the obtained results are perfectly analogous to Luo-Stong' ones, and may be proved with little effort by means of edge-coloured graphs representing manifolds.

Los estilos APA, Harvard, Vancouver, ISO, etc.

Ofrecemos descuentos en todos los planes premium para autores cuyas obras están incluidas en selecciones literarias temáticas. ¡Contáctenos para obtener un código promocional único!