Log in

Relevant bibliographies by topics / Edge-coloured graph / Journal articles

Journal articles on the topic 'Edge-coloured graph'

To see the other types of publications on this topic, follow the link: Edge-coloured graph.

Author: Grafiati

Published: 25 May 2024

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles

Select a source type:

Consult the top 50 journal articles for your research on the topic 'Edge-coloured graph.'

Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.

You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.

Browse journal articles on a wide variety of disciplines and organise your bibliography correctly.

1

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

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

2

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

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

3

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

Full text

Abstract:

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

APA, Harvard, Vancouver, ISO, and other styles

4

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

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

5

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

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

6

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

Full text

APA, Harvard, Vancouver, ISO, and other styles

7

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

Full text

Abstract:

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

APA, Harvard, Vancouver, ISO, and other styles

8

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

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

9

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

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

10

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

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

11

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

Full text

Abstract:

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

APA, Harvard, Vancouver, ISO, and other styles

12

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

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

13

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

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

14

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

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

15

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

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

16

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

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

17

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

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

18

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

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

19

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

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

20

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

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

21

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

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

22

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

Full text

Abstract:

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

APA, Harvard, Vancouver, ISO, and other styles

23

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

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

24

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

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

25

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

Full text

Abstract:

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

APA, Harvard, Vancouver, ISO, and other styles

26

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

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

27

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

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

28

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

Full text

APA, Harvard, Vancouver, ISO, and other styles

29

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

Full text

APA, Harvard, Vancouver, ISO, and other styles

30

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

Full text

APA, Harvard, Vancouver, ISO, and other styles

31

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

Full text

APA, Harvard, Vancouver, ISO, and other styles

32

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

Full text

APA, Harvard, Vancouver, ISO, and other styles

33

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

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

34

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

Full text

APA, Harvard, Vancouver, ISO, and other styles

35

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

Full text

APA, Harvard, Vancouver, ISO, and other styles

36

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

Full text

APA, Harvard, Vancouver, ISO, and other styles

37

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

Full text

APA, Harvard, Vancouver, ISO, and other styles

38

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

Full text

APA, Harvard, Vancouver, ISO, and other styles

39

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

Full text

APA, Harvard, Vancouver, ISO, and other styles

40

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

Full text

APA, Harvard, Vancouver, ISO, and other styles

41

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

Full text

APA, Harvard, Vancouver, ISO, and other styles

42

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

Full text

APA, Harvard, Vancouver, ISO, and other styles

43

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

Full text

APA, Harvard, Vancouver, ISO, and other styles

44

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

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

45

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

Full text

APA, Harvard, Vancouver, ISO, and other styles

46

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

Full text

APA, Harvard, Vancouver, ISO, and other styles

47

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

Full text

APA, Harvard, Vancouver, ISO, and other styles

48

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

Full text

APA, Harvard, Vancouver, ISO, and other styles

49

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

Full text

APA, Harvard, Vancouver, ISO, and other styles

50

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

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

We offer discounts on all premium plans for authors whose works are included in thematic literature selections. Contact us to get a unique promo code!