Log in

Relevant bibliographies by topics / Edge-coloured graph

Contents

Journal articles
Dissertations / Theses
Book chapters
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, 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 (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 (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 (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 (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 couleurs. Malgré son origine théorique, la coloration des graphes a trouvé de nombreuses applications pratiques telles que la planification, les problèmes d'assignation de fréquences, la segmentation, etc. Le Problème des Quatre Couleurs est l'un des problèmes importants parmi de nombreux problèmes de la théorie des graphes chromatiques, à partir duquel de nombreuses variantes et généralisations ont été proposées. Tout d'abord, dans cette thèse, nous visons à optimiser la stratégie de coloration des sommets de graphes et d'hypergraphes avec certaines contraintes données, en combinant le concept de coloration propre et d'élément représentatif de certains sous-ensembles de sommets. D'autre part, en fonction du sujet à colorer, une grande quantité de recherches et de problèmes de graphes à arêtes colorées ont émergé, avec des applications importantes en biologie et en technologies web. Nous fournissons quelques résultats analogues pour certaines questions de connectivité, afin de décrire des graphes dont les arêtes sont attribuées suffisamment de couleurs, garantissant ainsi des arbres couvrants ou des cycles ayant une structure chromatique spécifique<br>Graph colouring is one of the best known, popular and extensively researched subject in the field of graph theory, having a wide literature with approaches from many domains and a lot of problems, which are still open and studied by various mathematicians and computer scientists along the world. The Four Colour Problem, originating the study of graph colouring, was one of the central problem in graph theory in the last century, which asks if it is possible to colour every planar graph properly by four colours. Despite the theoretical origin, the graph colouring has found many applications in practice like scheduling, frequency assignment problems, segmentation, etc. The Four Colour Problem is a significant one among many problems in chromatic graph theory, from which many variants and generalizations have been proposed. Firstly, in this thesis, we aim to optimize the strategy to colour the vertex of graphs and hypergraphs with some given constraints, which combines the concept of proper colouring and representative element of some vertex subsets. On the other hand, according to the subject to be coloured, a large amount of research and problems of edge-coloured graphs have emerged, which have important applications to biology and web technologies. We provide some analogous results for some connectivity issues—to describe graphs whose edges are assigned enough colours, that guarantee spanning trees or cycles of a specific chromatic structure

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 cycles of all lengths between 4 and n/2 (rounded up). This answers a conjecture of Li, Nikiforov and Schelp. Attention will then turn to the length of the longest monochromatic cycle in a 2-edge-coloured graph with minimal degree at least cn. In particular, a lower bound for this quantity will be proved which is asymptotically best possible. The next chapter of the thesis then shows that a hamiltonian graph with minimal degree at least (5-sqrt7)n/6 contains a 2-factor with two components. The thesis then concludes with a chapter about X_H, which is the number of copies of a graph H in the random graph G(n,p). In particular, it will be shown that, for a connected graph H, the value of X_H modulo k is approximately uniformly distributed, provided that k is not too large a function of n.

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 simple graphs. Fi- nally, we also present some results on total colouring.

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!