Conecte-se

Bibliografias temáticas / Edge-coloured graph / Artigos de revistas

Artigos de revistas sobre o tema "Edge-coloured graph"

Siga este link para ver outros tipos de publicações sobre o tema: Edge-coloured graph.

Autor: Grafiati

Publicado: 25 de maio de 2024

Crie uma referência precisa em APA, MLA, Chicago, Harvard, e outros estilos

Selecione um tipo de fonte:

Veja os 50 melhores artigos de revistas para estudos sobre o assunto "Edge-coloured graph".

Ao lado de cada fonte na lista de referências, há um botão "Adicionar à bibliografia". Clique e geraremos automaticamente a citação bibliográfica do trabalho escolhido no estilo de citação de que você precisa: APA, MLA, Harvard, Chicago, Vancouver, etc.

Você também pode baixar o texto completo da publicação científica em formato .pdf e ler o resumo do trabalho online se estiver presente nos metadados.

Veja os artigos de revistas das mais diversas áreas científicas e compile uma bibliografia correta.

1

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

Texto completo da fonte

Resumo:

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.

Estilos ABNT, Harvard, Vancouver, APA, etc.

2

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

Texto completo da fonte

Resumo:

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.

Estilos ABNT, Harvard, Vancouver, APA, etc.

3

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

Texto completo da fonte

Resumo:

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].

Estilos ABNT, Harvard, Vancouver, APA, etc.

4

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

Texto completo da fonte

Resumo:

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.

Estilos ABNT, Harvard, Vancouver, APA, etc.

5

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

Texto completo da fonte

Resumo:

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.

Estilos ABNT, Harvard, Vancouver, APA, etc.

6

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

Texto completo da fonte

Estilos ABNT, Harvard, Vancouver, APA, 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 (março de 2021): 25–29. http://dx.doi.org/10.18173/2354-1059.2021-0003.

Texto completo da fonte

Resumo:

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].

Estilos ABNT, Harvard, Vancouver, APA, etc.

8

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

Texto completo da fonte

Resumo:

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.

Estilos ABNT, Harvard, Vancouver, APA, etc.

9

Piejko, Krzysztof, e 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 da fonte

Resumo:

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.

Estilos ABNT, Harvard, Vancouver, APA, etc.

10

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

Texto completo da fonte

Resumo:

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.

Estilos ABNT, Harvard, Vancouver, APA, etc.

11

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

Texto completo da fonte

Resumo:

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

Estilos ABNT, Harvard, Vancouver, APA, etc.

12

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

Texto completo da fonte

Resumo:

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.

Estilos ABNT, Harvard, Vancouver, APA, etc.

13

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

Texto completo da fonte

Resumo:

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.

Estilos ABNT, Harvard, Vancouver, APA, etc.

14

Nguyen Thi Thuy, Anh, e 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 (outubro de 2021): 3–7. http://dx.doi.org/10.18173/2354-1059.2021-0041.

Texto completo da fonte

Resumo:

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.

Estilos ABNT, Harvard, Vancouver, APA, etc.

15

Král’, Daniel, Edita Máčajov´, Attila Pór e 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 da fonte

Resumo:

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.

Estilos ABNT, Harvard, Vancouver, APA, etc.

16

Brunetti, Maurizio, e 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 da fonte

Resumo:

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.

Estilos ABNT, Harvard, Vancouver, APA, etc.

17

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

Texto completo da fonte

Resumo:

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.

Estilos ABNT, Harvard, Vancouver, APA, 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 (setembro de 1996): 297–306. http://dx.doi.org/10.1017/s0963548300002054.

Texto completo da fonte

Resumo:

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.

Estilos ABNT, Harvard, Vancouver, APA, etc.

19

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

Texto completo da fonte

Resumo:

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.

Estilos ABNT, Harvard, Vancouver, APA, etc.

20

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

Texto completo da fonte

Resumo:

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.

Estilos ABNT, Harvard, Vancouver, APA, etc.

21

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

Texto completo da fonte

Resumo:

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.

Estilos ABNT, Harvard, Vancouver, APA, etc.

22

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

Texto completo da fonte

Resumo:

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ℤ.

Estilos ABNT, Harvard, Vancouver, APA, etc.

23

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

Texto completo da fonte

Resumo:

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.

Estilos ABNT, Harvard, Vancouver, APA, etc.

24

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

Texto completo da fonte

Resumo:

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.

Estilos ABNT, Harvard, Vancouver, APA, etc.

25

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

Texto completo da fonte

Resumo:

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 → ∞.

Estilos ABNT, Harvard, Vancouver, APA, etc.

26

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

Texto completo da fonte

Resumo:

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.

Estilos ABNT, Harvard, Vancouver, APA, etc.

27

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

Texto completo da fonte

Resumo:

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.

Estilos ABNT, Harvard, Vancouver, APA, etc.

28

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

Texto completo da fonte

Estilos ABNT, Harvard, Vancouver, APA, etc.

29

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

Texto completo da fonte

Estilos ABNT, Harvard, Vancouver, APA, etc.

30

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

Texto completo da fonte

Estilos ABNT, Harvard, Vancouver, APA, etc.

31

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

Texto completo da fonte

Estilos ABNT, Harvard, Vancouver, APA, 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 da fonte

Estilos ABNT, Harvard, Vancouver, APA, etc.

33

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

Texto completo da fonte

Resumo:

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.

Estilos ABNT, Harvard, Vancouver, APA, etc.

34

Kanté, Mamadou Moustapha, e 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 da fonte

Estilos ABNT, Harvard, Vancouver, APA, etc.

35

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

Texto completo da fonte

Estilos ABNT, Harvard, Vancouver, APA, etc.

36

Idzik, Adam, Jan Komar e 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 da fonte

Estilos ABNT, Harvard, Vancouver, APA, etc.

37

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

Texto completo da fonte

Estilos ABNT, Harvard, Vancouver, APA, etc.

38

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

Texto completo da fonte

Estilos ABNT, Harvard, Vancouver, APA, 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 da fonte

Estilos ABNT, Harvard, Vancouver, APA, etc.

40

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

Texto completo da fonte

Estilos ABNT, Harvard, Vancouver, APA, etc.

41

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

Texto completo da fonte

Estilos ABNT, Harvard, Vancouver, APA, etc.

42

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

Texto completo da fonte

Estilos ABNT, Harvard, Vancouver, APA, etc.

43

Pokrovskiy, Alexey, e 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 da fonte

Estilos ABNT, Harvard, Vancouver, APA, etc.

44

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

Texto completo da fonte

Resumo:

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.

Estilos ABNT, Harvard, Vancouver, APA, etc.

45

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

Texto completo da fonte

Estilos ABNT, Harvard, Vancouver, APA, etc.

46

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

Texto completo da fonte

Estilos ABNT, Harvard, Vancouver, APA, etc.

47

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

Texto completo da fonte

Estilos ABNT, Harvard, Vancouver, APA, etc.

48

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

Texto completo da fonte

Estilos ABNT, Harvard, Vancouver, APA, etc.

49

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

Texto completo da fonte

Estilos ABNT, Harvard, Vancouver, APA, etc.

50

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

Texto completo da fonte

Resumo:

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.

Estilos ABNT, Harvard, Vancouver, APA, etc.

Oferecemos descontos em todos os planos premium para autores cujas obras estão incluídas em seleções literárias temáticas. Contate-nos para obter um código promocional único!