Zaloguj się

Gotowe bibliografie tematyczne / Edge-coloured graph / Artykuły w czasopismach

Artykuły w czasopismach na temat „Edge-coloured graph”

Kliknij ten link, aby zobaczyć inne rodzaje publikacji na ten temat: Edge-coloured graph.

Autor: Grafiati

Data publikacji: 25 maja 2024

Utwórz poprawne odniesienie w stylach APA, MLA, Chicago, Harvard i wielu innych

Wybierz rodzaj źródła:

Sprawdź 50 najlepszych artykułów w czasopismach naukowych na temat „Edge-coloured graph”.

Przycisk „Dodaj do bibliografii” jest dostępny obok każdej pracy w bibliografii. Użyj go – a my automatycznie utworzymy odniesienie bibliograficzne do wybranej pracy w stylu cytowania, którego potrzebujesz: APA, MLA, Harvard, Chicago, Vancouver itp.

Możesz również pobrać pełny tekst publikacji naukowej w formacie „.pdf” i przeczytać adnotację do pracy online, jeśli odpowiednie parametry są dostępne w metadanych.

Przeglądaj artykuły w czasopismach z różnych dziedzin i twórz odpowiednie bibliografie.

1

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

Pełny tekst źródła

Streszczenie:

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.

Style APA, Harvard, Vancouver, ISO itp.

2

KOSTOCHKA, ALEXANDR, i MATTHEW YANCEY. "Large Rainbow Matchings in Edge-Coloured Graphs". Combinatorics, Probability and Computing 21, nr 1-2 (2.02.2012): 255–63. http://dx.doi.org/10.1017/s0963548311000605.

Pełny tekst źródła

Streszczenie:

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.

Style APA, Harvard, Vancouver, ISO itp.

3

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

Pełny tekst źródła

Streszczenie:

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

Style APA, Harvard, Vancouver, ISO itp.

4

DIAO, Y., i G. HETYEI. "Relative Tutte Polynomials of Tensor Products of Coloured Graphs". Combinatorics, Probability and Computing 22, nr 6 (4.09.2013): 801–28. http://dx.doi.org/10.1017/s0963548313000370.

Pełny tekst źródła

Streszczenie:

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.

Style APA, Harvard, Vancouver, ISO itp.

5

KITTIPASSORN, TEERADEJ, i BHARGAV P. NARAYANAN. "A Canonical Ramsey Theorem for Exactly m-Coloured Complete Subgraphs". Combinatorics, Probability and Computing 23, nr 1 (18.10.2013): 102–15. http://dx.doi.org/10.1017/s0963548313000503.

Pełny tekst źródła

Streszczenie:

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.

Style APA, Harvard, Vancouver, ISO itp.

6

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

Pełny tekst źródła

Style APA, Harvard, Vancouver, ISO itp.

7

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

Pełny tekst źródła

Streszczenie:

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

Style APA, Harvard, Vancouver, ISO itp.

8

Fujita, Shinya, Ruonan Li i Guanghui Wang. "Decomposing edge-coloured graphs under colour degree constraints". Combinatorics, Probability and Computing 28, nr 5 (1.03.2019): 755–67. http://dx.doi.org/10.1017/s0963548319000014.

Pełny tekst źródła

Streszczenie:

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.

Style APA, Harvard, Vancouver, ISO itp.

9

Piejko, Krzysztof, i 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.

Pełny tekst źródła

Streszczenie:

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.

Style APA, Harvard, Vancouver, ISO itp.

10

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

Pełny tekst źródła

Streszczenie:

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.

Style APA, Harvard, Vancouver, ISO itp.

11

Rahayuningtyas, Handrini, Abdussakir Abdussakir i Achmad Nashichuddin. "Bilangan Kromatik Grap Commuting dan Non Commuting Grup Dihedral". CAUCHY 4, nr 1 (15.11.2015): 16. http://dx.doi.org/10.18860/ca.v4i1.3169.

Pełny tekst źródła

Streszczenie:

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

Style APA, Harvard, Vancouver, ISO itp.

12

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

Pełny tekst źródła

Streszczenie:

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.

Style APA, Harvard, Vancouver, ISO itp.

13

LETZTER, SHOHAM. "Path Ramsey Number for Random Graphs". Combinatorics, Probability and Computing 25, nr 4 (7.12.2015): 612–22. http://dx.doi.org/10.1017/s0963548315000279.

Pełny tekst źródła

Streszczenie:

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.

Style APA, Harvard, Vancouver, ISO itp.

14

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

Pełny tekst źródła

Streszczenie:

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.

Style APA, Harvard, Vancouver, ISO itp.

15

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

Pełny tekst źródła

Streszczenie:

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.

Style APA, Harvard, Vancouver, ISO itp.

16

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

Pełny tekst źródła

Streszczenie:

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.

Style APA, Harvard, Vancouver, ISO itp.

17

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

Pełny tekst źródła

Streszczenie:

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.

Style APA, Harvard, Vancouver, ISO itp.

18

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

Pełny tekst źródła

Streszczenie:

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.

Style APA, Harvard, Vancouver, ISO itp.

19

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

Pełny tekst źródła

Streszczenie:

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.

Style APA, Harvard, Vancouver, ISO itp.

20

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

Pełny tekst źródła

Streszczenie:

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.

Style APA, Harvard, Vancouver, ISO itp.

21

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

Pełny tekst źródła

Streszczenie:

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.

Style APA, Harvard, Vancouver, ISO itp.

22

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

Pełny tekst źródła

Streszczenie:

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

Style APA, Harvard, Vancouver, ISO itp.

23

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

Pełny tekst źródła

Streszczenie:

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.

Style APA, Harvard, Vancouver, ISO itp.

24

Gao, Pu, Reshma Ramadurai, Ian M. Wanless i Nick Wormald. "Full rainbow matchings in graphs and hypergraphs". Combinatorics, Probability and Computing 30, nr 5 (20.01.2021): 762–80. http://dx.doi.org/10.1017/s0963548320000620.

Pełny tekst źródła

Streszczenie:

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.

Style APA, Harvard, Vancouver, ISO itp.

25

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

Pełny tekst źródła

Streszczenie:

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

Style APA, Harvard, Vancouver, ISO itp.

26

BOUSQUET, NICOLAS, LOUIS ESPERET, ARARAT HARUTYUNYAN i RÉMI DE JOANNIS DE VERCLOS. "Exact Distance Colouring in Trees". Combinatorics, Probability and Computing 28, nr 2 (24.07.2018): 177–86. http://dx.doi.org/10.1017/s0963548318000378.

Pełny tekst źródła

Streszczenie:

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.

Style APA, Harvard, Vancouver, ISO itp.

27

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

Pełny tekst źródła

Streszczenie:

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.

Style APA, Harvard, Vancouver, ISO itp.

28

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

Pełny tekst źródła

Style APA, Harvard, Vancouver, ISO itp.

29

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

Pełny tekst źródła

Style APA, Harvard, Vancouver, ISO itp.

30

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

Pełny tekst źródła

Style APA, Harvard, Vancouver, ISO itp.

31

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

Pełny tekst źródła

Style APA, Harvard, Vancouver, ISO itp.

32

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

Pełny tekst źródła

Style APA, Harvard, Vancouver, ISO itp.

33

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

Pełny tekst źródła

Streszczenie:

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.

Style APA, Harvard, Vancouver, ISO itp.

34

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

Pełny tekst źródła

Style APA, Harvard, Vancouver, ISO itp.

35

Casali, Maria Rita, i Luigi Grasselli. "Representing branched coverings by Edge-Coloured Graphs". Topology and its Applications 33, nr 2 (październik 1989): 197–207. http://dx.doi.org/10.1016/s0166-8641(89)80008-2.

Pełny tekst źródła

Style APA, Harvard, Vancouver, ISO itp.

36

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

Pełny tekst źródła

Style APA, Harvard, Vancouver, ISO itp.

37

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

Pełny tekst źródła

Style APA, Harvard, Vancouver, ISO itp.

38

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

Pełny tekst źródła

Style APA, Harvard, Vancouver, ISO itp.

39

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

Pełny tekst źródła

Style APA, Harvard, Vancouver, ISO itp.

40

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

Pełny tekst źródła

Style APA, Harvard, Vancouver, ISO itp.

41

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

Pełny tekst źródła

Style APA, Harvard, Vancouver, ISO itp.

42

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

Pełny tekst źródła

Style APA, Harvard, Vancouver, ISO itp.

43

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

Pełny tekst źródła

Style APA, Harvard, Vancouver, ISO itp.

44

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

Pełny tekst źródła

Streszczenie:

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.

Style APA, Harvard, Vancouver, ISO itp.

45

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

Pełny tekst źródła

Style APA, Harvard, Vancouver, ISO itp.

46

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

Pełny tekst źródła

Style APA, Harvard, Vancouver, ISO itp.

47

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

Pełny tekst źródła

Style APA, Harvard, Vancouver, ISO itp.

48

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

Pełny tekst źródła

Style APA, Harvard, Vancouver, ISO itp.

49

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

Pełny tekst źródła

Style APA, Harvard, Vancouver, ISO itp.

50

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

Pełny tekst źródła

Streszczenie:

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.

Style APA, Harvard, Vancouver, ISO itp.

Oferujemy zniżki na wszystkie plany premium dla autorów, których prace zostały uwzględnione w tematycznych zestawieniach literatury. Skontaktuj się z nami, aby uzyskać unikalny kod promocyjny!