Добірка наукової літератури з теми "Anti-Ramsey number"

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.

A subgraph H of an edge-colored graph G is called rainbow if all of its edges have different colors. Let ar(G,H) denote the maximum positive integer t, such that there is a t-edge-colored graph G without any rainbow subgraph H. We denote by kK2 a matching of size k and On the class of all maximal outer-planar graphs on n vertices, respectively. The outer-planar anti-Ramsey number of graph H, denoted by ar(On,H), is defined as max{ar(On,H)|On∈On}. It seems nontrivial to determine the exact values for ar(On,H) because most maximal outer-planar graphs are asymmetry. In this paper, we obtain that ar(On,kK2)≤n+3k−8 for all n≥2k and k≥6, which improves the existing upper bound for ar(On,kK2), and prove that ar(On,kK2)=n+2k−5 for n=2k and k≥5. We also obtain that ar(On,6K2)=n+6 for all n≥29.

Let [Formula: see text] be a family of graphs. The anti-Ramsey number [Formula: see text] for [Formula: see text] in the graph [Formula: see text] is the maximum number of colors in an edge coloring of [Formula: see text] that does not have any rainbow copy of any graph in [Formula: see text]. In this paper, we consider the anti-Ramsey number for matchings in regular bipartite graphs and determine its value under several conditions.

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

The anti-Ramsey number ar(G,H) with input graph G and pattern graph H, is the maximum positive integer k such that there exists an edge coloring of G using k colors, in which there are no rainbow subgraphs isomorphic to H in G. (H is rainbow if all its edges get distinct colors). The concept of anti-Ramsey number was introduced by Erdos, Simanovitz, and Sos in 1973. Thereafter several researchers investigated this concept in the combinatorial setting. The cases where pattern graph H is a complete graph K_r, a path P_r or a star K_{1,r} for a fixed positive integer r, are well studied.Recently, Feng et al. revisited the anti-Ramsey problem for the pattern graph K_{1,t} (for t geq 3) purely from an algorithmic point of view, due to its applications in interference modeling of wireless networks. They posed it as an optimization problem, the maximum edge q-coloring problem. For a graph G and an integer q geq 2, an edge q-coloring of G is an assignment of colors to edges of G, such that edges incident on a vertex span at most q distinct colors. The maximum edge q-coloring problem seeks to maximize the number of colors in an edge q- coloring of the graph G. Note that the optimum value of the edge q-coloring problem of G equals ar(G,K_{1,q+1}). We study ar(G,K_{1,t}), the anti-Ramsey number of stars, for each fixed integer t geq 3, both from combinatorial and algorithmic point of view. The first of our main results, presents an upper bound for ar(G,K_{1,q+1}), in terms of number of vertices and the minimum degree of G. The second one improves this result for the case of triangle free input graphs. For a positive integer t, let H_t denote a subgraph of G with maximum number of possible edges and maximum degree t. From an observation of Erdos, Simanovitz, and Sos, we get: |E(H_{q-1})| + 1 leq ar(G,K_{1,q+1}) leq |E(H_{q})|. For instance, when q=2, the subgraph E(H_{q-1}) refers to a maximum matching. It looks like |E(H_{q-1})| is the most natural parameter associated with the anti-ramsey number ar(G,K_{1,q+1}) and the approximation algorithms for the maximum edge coloring problem proceed usually by first computing the H_{q-1}, then coloring all its edges with different colors and by giving one (sometimes more than one) extra colors to the remaining edges. The approximation guarantees of these algorithms usually depend on upper bounds for ar(G,K_{1,q+1}) in terms of |E(H_{q-1})|. Our third main result presents an upper bound for ar(G,K_{1,q+1}) in terms of |E(H_{q-1})|. All our results have algorithmic consequences. For some large special classes of graphs, such as d-regular graphs, where d geq 4, our results can be used to prove a better approximation guarantee for the sub-factor based algorithm. We also show that all our bounds are almost tight. Results for the case q=2 were done earlier by Chandran et al. In this thesis, we extend it further for each fixed integer q greater then 2