Bibliografías temáticas / Edge-coloured graph

Índice

Artículos de revistas
Tesis
Capítulos de libros
Actas de conferencias

Literatura académica sobre el tema "Edge-coloured graph"

Autor: Grafiati

Publicado: 25 de mayo de 2024

Crea una cita precisa en los estilos APA, MLA, Chicago, Harvard y otros

Elija tipo de fuente:

Consulte las listas temáticas de artículos, libros, tesis, actas de conferencias y otras fuentes académicas sobre el tema "Edge-coloured graph".

Junto a cada fuente en la lista de referencias hay un botón "Agregar a la bibliografía". Pulsa este botón, y generaremos automáticamente la referencia bibliográfica para la obra elegida en el estilo de cita que necesites: APA, MLA, Harvard, Vancouver, Chicago, etc.

También puede descargar el texto completo de la publicación académica en formato pdf y leer en línea su resumen siempre que esté disponible en los metadatos.

Artículos de revistas sobre el tema "Edge-coloured graph"

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

Texto completo

Resumen

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.

Los estilos APA, Harvard, Vancouver, ISO, etc.

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

Texto completo

Resumen

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.

Los estilos APA, Harvard, Vancouver, ISO, etc.

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

Texto completo

Resumen

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

Los estilos APA, Harvard, Vancouver, ISO, etc.

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

Texto completo

Resumen

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.

Los estilos APA, Harvard, Vancouver, ISO, etc.

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

Texto completo

Resumen

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.

Los estilos APA, Harvard, Vancouver, ISO, etc.

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

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

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

Texto completo

Resumen

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

Los estilos APA, Harvard, Vancouver, ISO, etc.

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

Texto completo

Resumen

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.

Los estilos APA, Harvard, Vancouver, ISO, etc.

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

Texto completo

Resumen

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.

Los estilos APA, Harvard, Vancouver, ISO, etc.

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

Texto completo

Resumen

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.

Los estilos APA, Harvard, Vancouver, ISO, etc.

Más fuentes

Tesis sobre el tema "Edge-coloured graph"

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.

Texto completo

Resumen

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

Los estilos APA, Harvard, Vancouver, ISO, etc.

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.

Texto completo

Resumen

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.

Los estilos APA, Harvard, Vancouver, ISO, etc.

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.

Texto completo

Resumen

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.

Los estilos APA, Harvard, Vancouver, ISO, etc.

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.

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

Capítulos de libros sobre el tema "Edge-coloured graph"

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

Texto completo

Resumen

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.

Los estilos APA, Harvard, Vancouver, ISO, etc.

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

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

Actas de conferencias sobre el tema "Edge-coloured graph"

Zatesko, Leandro M., Renato Carmo y André L. P. Guedes. "Novel Procedures for Graph Edge-colouring". En 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.

Texto completo

Resumen

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.

Los estilos APA, Harvard, Vancouver, ISO, etc.

Ofrecemos descuentos en todos los planes premium para autores cuyas obras están incluidas en selecciones literarias temáticas. ¡Contáctenos para obtener un código promocional único!