Einloggen

Thematische Bibliographien / Edge-coloured graph / Zeitschriftenartikel

Um die anderen Arten von Veröffentlichungen zu diesem Thema anzuzeigen, folgen Sie diesem Link: Edge-coloured graph.

Zeitschriftenartikel zum Thema „Edge-coloured graph“

Autor: Grafiati

Veröffentlicht am 25. Mai 2024

Geben Sie eine Quelle nach APA, MLA, Chicago, Harvard und anderen Zitierweisen an

Wählen Sie eine Art der Quelle aus:

Machen Sie sich mit Top-50 Zeitschriftenartikel für die Forschung zum Thema "Edge-coloured graph" bekannt.

Neben jedem Werk im Literaturverzeichnis ist die Option "Zur Bibliographie hinzufügen" verfügbar. Nutzen Sie sie, wird Ihre bibliographische Angabe des gewählten Werkes nach der nötigen Zitierweise (APA, MLA, Harvard, Chicago, Vancouver usw.) automatisch gestaltet.

Sie können auch den vollen Text der wissenschaftlichen Publikation im PDF-Format herunterladen und eine Online-Annotation der Arbeit lesen, wenn die relevanten Parameter in den Metadaten verfügbar sind.

Sehen Sie die Zeitschriftenartikel für verschiedene Spezialgebieten durch und erstellen Sie Ihre Bibliographie auf korrekte Weise.

1

COOPER, COLIN, und ALAN FRIEZE. „Multi-Coloured Hamilton Cycles in Random Edge-Coloured Graphs“. Combinatorics, Probability and Computing 11, Nr. 2 (März 2002): 129–33. http://dx.doi.org/10.1017/s0963548301005004.

Der volle Inhalt der Quelle

Annotation:

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 und andere Zitierweisen

2

KOSTOCHKA, ALEXANDR, und MATTHEW YANCEY. „Large Rainbow Matchings in Edge-Coloured Graphs“. Combinatorics, Probability and Computing 21, Nr. 1-2 (02.02.2012): 255–63. http://dx.doi.org/10.1017/s0963548311000605.

Der volle Inhalt der Quelle

Annotation:

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 und andere Zitierweisen

3

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

Der volle Inhalt der Quelle

Annotation:

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 und andere Zitierweisen

4

DIAO, Y., und G. HETYEI. „Relative Tutte Polynomials of Tensor Products of Coloured Graphs“. Combinatorics, Probability and Computing 22, Nr. 6 (04.09.2013): 801–28. http://dx.doi.org/10.1017/s0963548313000370.

Der volle Inhalt der Quelle

Annotation:

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 und andere Zitierweisen

5

KITTIPASSORN, TEERADEJ, und 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.

Der volle Inhalt der Quelle

Annotation:

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 und andere Zitierweisen

6

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

Der volle Inhalt der Quelle

APA, Harvard, Vancouver, ISO und andere Zitierweisen

7

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

Der volle Inhalt der Quelle

Annotation:

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 und andere Zitierweisen

8

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

Der volle Inhalt der Quelle

Annotation:

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 und andere Zitierweisen

9

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

Der volle Inhalt der Quelle

Annotation:

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 und andere Zitierweisen

10

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

Der volle Inhalt der Quelle

Annotation:

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 und andere Zitierweisen

11

Rahayuningtyas, Handrini, Abdussakir Abdussakir und 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.

Der volle Inhalt der Quelle

Annotation:

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 und andere Zitierweisen

12

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

Der volle Inhalt der Quelle

Annotation:

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 und andere Zitierweisen

13

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

Der volle Inhalt der Quelle

Annotation:

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 und andere Zitierweisen

14

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

Der volle Inhalt der Quelle

Annotation:

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 und andere Zitierweisen

15

Král’, Daniel, Edita Máčajov´, Attila Pór und 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 (01.04.2010): 355–81. http://dx.doi.org/10.4153/cjm-2010-021-9.

Der volle Inhalt der Quelle

Annotation:

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 und andere Zitierweisen

16

Brunetti, Maurizio, und 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.

Der volle Inhalt der Quelle

Annotation:

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 und andere Zitierweisen

17

MARCINISZYN, MARTIN, RETO SPÖHEL und ANGELIKA STEGER. „Online Ramsey Games in Random Graphs“. Combinatorics, Probability and Computing 18, Nr. 1-2 (März 2009): 271–300. http://dx.doi.org/10.1017/s0963548308009632.

Der volle Inhalt der Quelle

Annotation:

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 und andere Zitierweisen

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 (September 1996): 297–306. http://dx.doi.org/10.1017/s0963548300002054.

Der volle Inhalt der Quelle

Annotation:

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 und andere Zitierweisen

19

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

Der volle Inhalt der Quelle

Annotation:

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 und andere Zitierweisen

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.

Der volle Inhalt der Quelle

Annotation:

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 und andere Zitierweisen

21

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

Der volle Inhalt der Quelle

Annotation:

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 und andere Zitierweisen

22

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

Der volle Inhalt der Quelle

Annotation:

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 und andere Zitierweisen

23

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

Der volle Inhalt der Quelle

Annotation:

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 und andere Zitierweisen

24

Gao, Pu, Reshma Ramadurai, Ian M. Wanless und 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.

Der volle Inhalt der Quelle

Annotation:

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 und andere Zitierweisen

25

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

Der volle Inhalt der Quelle

Annotation:

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 und andere Zitierweisen

26

BOUSQUET, NICOLAS, LOUIS ESPERET, ARARAT HARUTYUNYAN und 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.

Der volle Inhalt der Quelle

Annotation:

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 und andere Zitierweisen

27

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

Der volle Inhalt der Quelle

Annotation:

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 und andere Zitierweisen

28

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

Der volle Inhalt der Quelle

APA, Harvard, Vancouver, ISO und andere Zitierweisen

29

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

Der volle Inhalt der Quelle

APA, Harvard, Vancouver, ISO und andere Zitierweisen

30

Bang-Jensen, J., G. Gutin und A. Yeo. „Properly coloured Hamiltonian paths in edge-coloured complete graphs“. Discrete Applied Mathematics 82, Nr. 1-3 (März 1998): 247–50. http://dx.doi.org/10.1016/s0166-218x(97)00062-0.

Der volle Inhalt der Quelle

APA, Harvard, Vancouver, ISO und andere Zitierweisen

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.

Der volle Inhalt der Quelle

APA, Harvard, Vancouver, ISO und andere Zitierweisen

32

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

Der volle Inhalt der Quelle

APA, Harvard, Vancouver, ISO und andere Zitierweisen

33

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

Der volle Inhalt der Quelle

Annotation:

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 und andere Zitierweisen

34

Kanté, Mamadou Moustapha, und 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.

Der volle Inhalt der Quelle

APA, Harvard, Vancouver, ISO und andere Zitierweisen

35

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

Der volle Inhalt der Quelle

APA, Harvard, Vancouver, ISO und andere Zitierweisen

36

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

Der volle Inhalt der Quelle

APA, Harvard, Vancouver, ISO und andere Zitierweisen

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.

Der volle Inhalt der Quelle

APA, Harvard, Vancouver, ISO und andere Zitierweisen

38

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

Der volle Inhalt der Quelle

APA, Harvard, Vancouver, ISO und andere Zitierweisen

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.

Der volle Inhalt der Quelle

APA, Harvard, Vancouver, ISO und andere Zitierweisen

40

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

Der volle Inhalt der Quelle

APA, Harvard, Vancouver, ISO und andere Zitierweisen

41

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

Der volle Inhalt der Quelle

APA, Harvard, Vancouver, ISO und andere Zitierweisen

42

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

Der volle Inhalt der Quelle

APA, Harvard, Vancouver, ISO und andere Zitierweisen

43

Pokrovskiy, Alexey, und 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.

Der volle Inhalt der Quelle

APA, Harvard, Vancouver, ISO und andere Zitierweisen

44

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

Der volle Inhalt der Quelle

Annotation:

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 und andere Zitierweisen

45

Lo, Allan, und 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.

Der volle Inhalt der Quelle

APA, Harvard, Vancouver, ISO und andere Zitierweisen

46

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

Der volle Inhalt der Quelle

APA, Harvard, Vancouver, ISO und andere Zitierweisen

47

Lang, Richard, Oliver Schaudt und 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.

Der volle Inhalt der Quelle

APA, Harvard, Vancouver, ISO und andere Zitierweisen

48

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

Der volle Inhalt der Quelle

APA, Harvard, Vancouver, ISO und andere Zitierweisen

49

Pokrovskiy, Alexey, und 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.

Der volle Inhalt der Quelle

APA, Harvard, Vancouver, ISO und andere Zitierweisen

50

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

Der volle Inhalt der Quelle

Annotation:

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 und andere Zitierweisen

Wir bieten Rabatte auf alle Premium-Pläne für Autoren, deren Werke in thematische Literatursammlungen aufgenommen wurden. Kontaktieren Sie uns, um einen einzigartigen Promo-Code zu erhalten!