Thematische Bibliographien / Edge-coloured graph

Inhaltsverzeichnis

Zeitschriftenartikel
Dissertationen
Buchteile
Konferenzberichte

Auswahl der wissenschaftlichen Literatur 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 den Listen der aktuellen Artikel, Bücher, Dissertationen, Berichten und anderer wissenschaftlichen Quellen 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.

Zeitschriftenartikel zum Thema "Edge-coloured graph"

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

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

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

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

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

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

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

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

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

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

Mehr Quellen

Dissertationen zum Thema "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.

Der volle Inhalt der Quelle

Annotation:

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

APA, Harvard, Vancouver, ISO und andere Zitierweisen

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.

Der volle Inhalt der Quelle

Annotation:

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

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.

Der volle Inhalt der Quelle

Annotation:

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

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.

Der volle Inhalt der Quelle

APA, Harvard, Vancouver, ISO und andere Zitierweisen

Buchteile zum Thema "Edge-coloured graph"

Beneš, Nikola, Luboš Brim, Samuel Pastva und David Šafránek. „Symbolic Coloured SCC Decomposition“. In 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.

Der volle Inhalt der Quelle

Annotation:

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

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

Der volle Inhalt der Quelle

APA, Harvard, Vancouver, ISO und andere Zitierweisen

Konferenzberichte zum Thema "Edge-coloured graph"

Zatesko, Leandro M., Renato Carmo und 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.

Der volle Inhalt der Quelle

Annotation:

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