Relevant bibliographies by topics / Edge-coloured graph

Contents

  1. Journal articles
  2. Dissertations / Theses
  3. Book chapters
  4. Conference papers

Academic literature on the topic '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 lists of relevant articles, books, theses, conference reports, and other scholarly sources 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.

Journal articles on the topic "Edge-coloured graph"

1

COOPER, COLIN, and ALAN FRIEZE. "Multi-Coloured Hamilton Cycles in Random Edge-Coloured Graphs." Combinatorics, Probability and Computing 11, no. 2 (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 (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, a
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 (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−
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 (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 z
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 (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 d
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 (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 (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 (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 (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

Dissertations / Theses on the topic "Edge-coloured graph"

1

Ouyang, Qiancheng. "Some colouring problems in edge/vertex-coloured graphs : Structural and extremal studies." Electronic Thesis or Diss., université Paris-Saclay, 2023. http://www.theses.fr/2023UPASG060.

Full text
Abstract:
La coloration de graphes est l'un des sujets les plus connus, populaires et largement étudiés dans le domaine de la théorie des graphes, avec une vaste littérature comprenant des approches provenant de nombreux domaines ainsi que de nombreux problèmes qui sont encore ouverts et étudiés par divers mathématiciens et informaticiens à travers le monde. Le Problème des Quatre Couleurs, à l'origine de l'étude de la coloration des graphes, a été l'un des problèmes centraux en théorie des graphes au siècle dernier. Il demande s'il est possible de colorer proprement chaque graphe planaire avec quatre c
APA, Harvard, Vancouver, ISO, and other styles
2

White, M. D. "Cycles in edge-coloured graphs and subgraphs of random graphs." Thesis, University of Oxford, 2011. http://ora.ox.ac.uk/objects/uuid:95ef351e-acb1-442c-adf5-970487e30a4d.

Full text
Abstract:
This thesis will study a variety of problems in graph theory. Initially, the focus will be on finding minimal degree conditions which guarantee the existence of various subgraphs. These subgraphs will all be formed of cycles, and this area of work will fall broadly into two main categories. First to be considered are cycles in edge-coloured graphs and, in particular, two questions of Li, Nikiforov and Schelp. It will be shown that a 2-edge-coloured graph with minimal degree at least 3n/4 either is isomorphic to the complete 4-partite graph with classes of order n/4, or contains monochromatic c
APA, Harvard, Vancouver, ISO, and other styles
3

Henderson, Matthew James. "Embedding Symmetric Latin Squares and Edge-Coloured graphs." Thesis, University of Reading, 2005. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.485356.

Full text
Abstract:
In this thesis the closely related problems of embedding symmetric latin rectangles and embedding properly edge-coloured complete graphs are considered. The thesis is divided into three parts. The first part is an introductio~ and survey about completing partial latin squares and embedding latin rectangles. The second part is a proof of a former conjecture of Dugdale and Hilton about embedding edge-coloured complete graphs and the third and final part is a partial generalisation of the second part to the problem of embedding symmetric latin squares.
APA, Harvard, Vancouver, ISO, and other styles
4

Rafiey-Hafshejani, Arash. "Extremal and optimization problems on dense directed and edge-coloured graphs." Thesis, Royal Holloway, University of London, 2006. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.435465.

Full text
APA, Harvard, Vancouver, ISO, and other styles

Book chapters on the topic "Edge-coloured graph"

1

Beneš, Nikola, Luboš Brim, Samuel Pastva, and David Šafránek. "Symbolic Coloured SCC Decomposition." In Tools and Algorithms for the Construction and Analysis of Systems. Springer International Publishing, 2021. http://dx.doi.org/10.1007/978-3-030-72013-1_4.

Full text
Abstract:
AbstractProblems arising in many scientific disciplines are often modelled using edge-coloured directed graphs. These can be enormous in the number of both vertices and colours. Given such a graph, the original problem frequently translates to the detection of the graph’s strongly connected components, which is challenging at this scale.We propose a new, symbolic algorithm that computes all the monochromatic strongly connected components of an edge-coloured graph. In the worst case, the algorithm performs $$O(p\cdot n\cdot \log n)$$ O ( p · n · log n ) symbolic steps, where p is the number of colours and n the number of vertices. We evaluate the algorithm using an experimental implementation based on Binary Decision Diagrams (BDDs) and large (up to $$2^{48}$$ 2 48 ) coloured graphs produced by models appearing in systems biology.
APA, Harvard, Vancouver, ISO, and other styles
2

Bang-Jensen, Jørgen, and Gregory Z. Gutin. "Applications of Digraphs and Edge-Coloured Graphs." In Springer Monographs in Mathematics. Springer London, 2009. http://dx.doi.org/10.1007/978-1-84800-998-1_17.

Full text
APA, Harvard, Vancouver, ISO, and other styles

Conference papers on the topic "Edge-coloured graph"

1

Zatesko, Leandro M., Renato Carmo, and André L. P. Guedes. "Novel Procedures for Graph Edge-colouring." In XXXII Concurso de Teses e Dissertações da SBC. Sociedade Brasileira de Computação - SBC, 2019. http://dx.doi.org/10.5753/ctd.2019.6331.

Full text
Abstract:
We present a novel recolouring procedure for graph edge-colouring. We show that all graphs whose vertices have local degree sum not too large can be optimally edge-coloured in polynomial time. We also show that the set ofthe graphs satisfying this condition includes almost every graph (under the uniform distribution). We present further results on edge-colouring join graphs, chordal graphs, circular-arc graphs, and complementary prisms, whose proofs yield polynomial-time algorithms. Our results contribute towards settling the Over- full Conjecture, the main open conjecture on edge-colouring si
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!

To the bibliography