Log in

Relevant bibliographies by topics / Maximum Edge Coloring (Graphs) / Dissertations / Theses

To see the other types of publications on this topic, follow the link: Maximum Edge Coloring (Graphs).

Dissertations / Theses on the topic 'Maximum Edge Coloring (Graphs)'

Author: Grafiati

Published: 4 June 2021

Last updated: 6 September 2023

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles

Select a source type:

Consult the top 27 dissertations / theses for your research on the topic 'Maximum Edge Coloring (Graphs).'

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.

Browse dissertations / theses on a wide variety of disciplines and organise your bibliography correctly.

1

Hocquard, Hervé. "Colorations de graphes sous contraintes." Phd thesis, Université Sciences et Technologies - Bordeaux I, 2011. http://tel.archives-ouvertes.fr/tel-00987686.

Full text

Abstract:

Dans cette thèse, nous nous intéressons à différentes notions de colorations sous contraintes. Nous nous intéressons plus spécialement à la coloration acyclique, à la coloration forte d'arêtes et à la coloration d'arêtes sommets adjacents distinguants.Dans le Chapitre 2, nous avons étudié la coloration acyclique. Tout d'abord nous avons cherché à borner le nombre chromatique acyclique pour la classe des graphes de degré maximum borné. Ensuite nous nous sommes attardés sur la coloration acyclique par listes. La notion de coloration acyclique par liste des graphes planaires a été introduite par

APA, Harvard, Vancouver, ISO, and other styles

2

Kurt, Oguz. "On The Coloring of Graphs." The Ohio State University, 2009. http://rave.ohiolink.edu/etdc/view?acc_num=osu1262287401.

Full text

APA, Harvard, Vancouver, ISO, and other styles

3

Gajewar, Amita Surendra. "Approximate edge 3-coloring of cubic graphs." Thesis, Atlanta, Ga. : Georgia Institute of Technology, 2008. http://hdl.handle.net/1853/29735.

Full text

Abstract:

Thesis (M. S.)--Computing, Georgia Institute of Technology, 2009.<br>Committee Chair: Prof. Richard Lipton; Committee Member: Prof. Dana Randall; Committee Member: Prof. H. Venkateswaran. Part of the SMARTech Electronic Thesis and Dissertation Collection.

APA, Harvard, Vancouver, ISO, and other styles

4

Macon, Lisa Fischer. "Almost regular graphs and edge-face colorings of plane graphs." Orlando, Fla. : University of Central Florida, 2009. http://purl.fcla.edu/fcla/etd/CFE0002507.

Full text

APA, Harvard, Vancouver, ISO, and other styles

5

Macon, Lisa. "ALMOST REGULAR GRAPHS AND EDGE FACE COLORINGS OF PLANE GRAPHS." Doctoral diss., University of Central Florida, 2009. http://digital.library.ucf.edu/cdm/ref/collection/ETD/id/2480.

Full text

Abstract:

Regular graphs are graphs in which all vertices have the same degree. Many properties of these graphs are known. Such graphs play an important role in modeling network configurations where equipment limitations impose a restriction on the maximum number of links emanating from a node. These limitations do not enforce strict regularity, and it becomes interesting to investigate nonregular graphs that are in some sense close to regular. This dissertation explores a particular class of almost regular graphs in detail and defines generalizations on this class. A linear-time algorithm for the creat

APA, Harvard, Vancouver, ISO, and other styles

6

Renman, Jonatan. "One-sided interval edge-colorings of bipartite graphs." Thesis, Linköpings universitet, Matematik och tillämpad matematik, 2020. http://urn.kb.se/resolve?urn=urn:nbn:se:liu:diva-171753.

Full text

Abstract:

A graph is an ordered pair composed by a set of vertices and a set of edges, the latter consisting of unordered pairs of vertices. Two vertices in such a pair are each others neighbors. Two edges are adjacent if they share a common vertex. Denote the amount of edges that share a specific vertex as the degree of the vertex. A proper edge-coloring of a graph is an assignment of colors from some finite set, to the edges of a graph where no two adjacent edges have the same color. A bipartition (X,Y) of a set of vertices V is an ordered pair of two disjoint sets of vertices such that V is the union

APA, Harvard, Vancouver, ISO, and other styles

7

SILVA, ANDERSON GOMES DA. "A STUDY ON EDGE AND TOTAL COLORING OF GRAPHS." PONTIFÍCIA UNIVERSIDADE CATÓLICA DO RIO DE JANEIRO, 2018. http://www.maxwell.vrac.puc-rio.br/Busca_etds.php?strSecao=resultado&nrSeq=36080@1.

Full text

Abstract:

PONTIFÍCIA UNIVERSIDADE CATÓLICA DO RIO DE JANEIRO<br>CONSELHO NACIONAL DE DESENVOLVIMENTO CIENTÍFICO E TECNOLÓGICO<br>Uma coloração de arestas é a atribuição de cores às arestas de um grafo, de modo que arestas adjacentes não recebam a mesma cor. O menor inteiro positivo para o qual um grafo admite uma coloração de arestas é dito seu índice cromático. Fizemos revisão bibliográfica dos principais resultados conhecidos nessa área. Uma coloração total, por sua vez, é a aplicação de cores aos vértices e arestas de um grafo de modo que elementos adjacentes ou incidentes recebam cores distintas. O

APA, Harvard, Vancouver, ISO, and other styles

8

HIRATA, Tomio, Takao ONO, and Xuzhen XIE. "On Approximation Algorithms for Coloring k-Colorable Graphs." Institute of Electronics, Information and Communication Engineers, 2003. http://hdl.handle.net/2237/15063.

Full text

APA, Harvard, Vancouver, ISO, and other styles

9

McClain, Christopher. "Edge colorings of graphs and multigraphs." Columbus, Ohio : Ohio State University, 2008. http://rave.ohiolink.edu/etdc/view?acc%5Fnum=osu1211904033.

Full text

APA, Harvard, Vancouver, ISO, and other styles

10

Chen, Min. "Vertex coloring of graphs via the discharging method." Thesis, Bordeaux 1, 2010. http://www.theses.fr/2010BOR14090/document.

Full text

Abstract:

Dans cette thèse, nous nous intéressons à differentes colorations des sommets d’un graphe et aux homomorphismes de graphes. Nous nous intéressons plus spécialement aux graphes planaires et aux graphes peu denses. Nous considérons la coloration propre des sommets, la coloration acyclique, la coloration étoilée, lak-forêt-coloration, la coloration fractionnaire et la version par liste de la plupart de ces concepts.Dans le Chapitre 2, nous cherchons des conditions suffisantes de 3-liste colorabilité des graphes planaires. Ces conditions sont exprimées en termes de sous-graphes interdits et nos ré

APA, Harvard, Vancouver, ISO, and other styles

11

Tahraoui, Mohammed Amin. "Coloring, packing and embedding of graphs." Phd thesis, Université Claude Bernard - Lyon I, 2012. http://tel.archives-ouvertes.fr/tel-00995041.

Full text

Abstract:

In this thesis, we investigate some problems in graph theory, namelythe graph coloring problem, the graph packing problem and tree pattern matchingfor XML query processing. The common point between these problems is that theyuse labeled graphs.In the first part, we study a new coloring parameter of graphs called the gapvertex-distinguishing edge coloring. It consists in an edge-coloring of a graph G whichinduces a vertex distinguishing labeling of G such that the label of each vertex isgiven by the difference between the highest and the lowest colors of its adjacentedges. The minimum number of

APA, Harvard, Vancouver, ISO, and other styles

12

Casselgren, Carl Johan. "On some graph coloring problems." Doctoral thesis, Umeå universitet, Institutionen för matematik och matematisk statistik, 2011. http://urn.kb.se/resolve?urn=urn:nbn:se:umu:diva-43389.

Full text

APA, Harvard, Vancouver, ISO, and other styles

13

Dross, François. "Vertex partition of sparse graphs." Thesis, Montpellier, 2018. http://www.theses.fr/2018MONTS011/document.

Full text

Abstract:

Le Théorème des Quatre Couleurs, conjecturé en 1852 et prouvé en 1976, est à l'origine de l'étude des partitions des sommets de graphes peu denses. Il affirme que toute carte plane peut être coloriée avec au plus quatre couleurs différentes, de telle manière que deux régions qui partagent une frontière aient des couleurs différentes. Énoncé en terme de théorie des graphes, cela veut dire que tout graphe planaire, c'est à dire tout graphe qui peut être représenté dans le plan sans que deux arêtes ne se croisent, peut voir son ensemble de sommets partitionné en quatre ensembles tels que chacun d

APA, Harvard, Vancouver, ISO, and other styles

14

Ma, Zongjie. "Searching on Massive Graphs and Regularizing Deep Learning." Thesis, Griffith University, 2018. http://hdl.handle.net/10072/385875.

Full text

Abstract:

We have designed di erent heuristics for both searching on Massive graphs and regularizing Deep Neural Networks in this work. Both the problem of nding a minimum vertex cover (MinVC) and the maximum edge weight clique (MEWC) in a graph are prominent NP-hard problems of great importance in both theory and application. During recent decades, there has been much interest in nding optimal or near-optimal solutions to these two problems. Many existing heuristic algorithms for MinVC are based on local search strategies. An algorithm called FastVC takes a rst step towards solving the MinVC problem

APA, Harvard, Vancouver, ISO, and other styles

15

Sinkovic, John Henry. "The Minimum Rank Problem for Outerplanar Graphs." BYU ScholarsArchive, 2013. https://scholarsarchive.byu.edu/etd/3722.

Full text

Abstract:

Given a simple graph G with vertex set V(G)={1,2,...,n} define S(G) to be the set of all real symmetric matrices A such that for all i not equal to j, the ijth entry of A is nonzero if and only if ij is in E(G). The range of the ranks of matrices in S(G) is of interest and can be determined by finding the minimum rank. The minimum rank of a graph, denoted mr(G), is the minimum rank achieved by a matrix in S(G). The maximum nullity of a graph, denoted M(G), is the maximum nullity achieved by a matrix in S(G). Note that mr(G)+M(G)=|V(G)| and so in finding the maximum nullity of a graph, the mini

APA, Harvard, Vancouver, ISO, and other styles

16

Borozan, Valentin. "Proper and weak-proper trees in edges-colored graphs and multigraphs." Phd thesis, Université Paris Sud - Paris XI, 2011. http://tel.archives-ouvertes.fr/tel-00738959.

Full text

Abstract:

Dans la présente thèse nous étudions l'extraction d'arbres dans des graphes arêtes-coloriés.Nous nous concentrons sur la recherche d'arbres couvrants proprement arête-coloriés et faiblement arête-coloriés, notée PST et WST. Nous montrons que les versions d'optimisation de ces problèmes sont NP-Complete dans le cas général des graphes arêtes-coloriés, et nous proposons des algorithmes pour trouver ces arbres dans le cas des graphes arêtes-coloriés sans cycles proprement arêtes-coloriés.Nous donnons également quelques limites de nonapproximabilité. Nous proposons des conditions suffisantes pour

APA, Harvard, Vancouver, ISO, and other styles

17

Morel, Gregory. "Stabilité et coloration des graphes sans P5." Thesis, Grenoble, 2011. http://www.theses.fr/2011GRENM042/document.

Full text

Abstract:

La classe des graphes sans P5, c'est-à-dire des graphes ne contenant pas de chaîne induite à cinq sommets, est d'un intérêt particulier en théorie des graphes. Il s'agit en effet de la plus petite classe définie par un seul sous-graphe connexe interdit pour laquelle on ignore encore s'il existe un algorithme polynomial permettant de résoudre le problème du stable maximum. Or ce problème, dont on sait qu'il est difficile en général, est d'une grande importance en pratique (problèmes de planification, d'allocation de registres dans un processeur, biologie moléculaire...). Dans cette thèse, nous

APA, Harvard, Vancouver, ISO, and other styles

18

Cruz, Jadder Bismarck de Sousa. "Coloração de Arestas em Grafos Split-Comparabilidade." Universidade Federal de São Carlos, 2017. https://repositorio.ufscar.br/handle/ufscar/9140.

Full text

Abstract:

Submitted by Milena Rubi (milenarubi@ufscar.br) on 2017-10-09T16:26:41Z No. of bitstreams: 1 CRUZ_Jadder_2017.pdf: 1326879 bytes, checksum: 61ee3c40e293d26085a939c0a0290716 (MD5)<br>Approved for entry into archive by Milena Rubi (milenarubi@ufscar.br) on 2017-10-09T16:26:55Z (GMT) No. of bitstreams: 1 CRUZ_Jadder_2017.pdf: 1326879 bytes, checksum: 61ee3c40e293d26085a939c0a0290716 (MD5)<br>Approved for entry into archive by Milena Rubi (milenarubi@ufscar.br) on 2017-10-09T16:27:03Z (GMT) No. of bitstreams: 1 CRUZ_Jadder_2017.pdf: 1326879 bytes, checksum: 61ee3c40e293d26085a939c0a0290716 (MD

APA, Harvard, Vancouver, ISO, and other styles

19

Goyal, Prachi. "Parameterized Complexity of Maximum Edge Coloring in Graphs." Thesis, 2012. https://etd.iisc.ac.in/handle/2005/3255.

Full text

Abstract:

The classical graph edge coloring problem deals in coloring the edges of a given graph with minimum number of colors such that no two adjacent edges in the graph, get the same color in the proposed coloring. In the following work, we look at the other end of the spectrum where in our goal is to maximize the number of colors used for coloring the edges of the graph under some vertex specific constraints. We deal with the MAXIMUM EDGE COLORING problem which is defined as the following –For an integer q ≥2 and a graph G, the goal is to find a coloring of the edges of G with the maximum number of

APA, Harvard, Vancouver, ISO, and other styles

20

Goyal, Prachi. "Parameterized Complexity of Maximum Edge Coloring in Graphs." Thesis, 2012. http://hdl.handle.net/2005/3255.

Full text

Abstract:

The classical graph edge coloring problem deals in coloring the edges of a given graph with minimum number of colors such that no two adjacent edges in the graph, get the same color in the proposed coloring. In the following work, we look at the other end of the spectrum where in our goal is to maximize the number of colors used for coloring the edges of the graph under some vertex specific constraints. We deal with the MAXIMUM EDGE COLORING problem which is defined as the following –For an integer q ≥2 and a graph G, the goal is to find a coloring of the edges of G with the maximum number of

APA, Harvard, Vancouver, ISO, and other styles

21

Hashim, Talha. "Improved approximation bounds on maximum edge q coloring of dense graphs." Thesis, 2023. https://etd.iisc.ac.in/handle/2005/6089.

Full text

Abstract:

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

APA, Harvard, Vancouver, ISO, and other styles

22

Chang, Chia-Fen, and 張嘉芬. "Edge-coloring of time graphs." Thesis, 1999. http://ndltd.ncl.edu.tw/handle/36799107986844744961.

Full text

Abstract:

碩士<br>東海大學<br>數學系<br>87<br>A graph G is called a time graph if its vertices can be put into one-to-one correspondence with a set of unit intervals of a linearly ordered set (like a real line) such that two vertices are connected by an edge of G if and only if their corresponding intervals have nonempty intersection. In this thesis, we mainly get that the graph G is of class 1 if maximum degree is odd. We also offer a conjecture in the third chapter to classify a time graph and get some results.

APA, Harvard, Vancouver, ISO, and other styles

23

Basavaraju, Manu. "Acyclic Edge Coloring Of Graphs." Thesis, 2010. https://etd.iisc.ac.in/handle/2005/2263.

Full text

Abstract:

A proper edge coloring of G =(V,E)is a map c : E → C (where C is the set of available colors ) with c(e) ≠ c(ƒ) for any adjacent edges e,f. The minimum number of colors needed to properly color the edges of G, is called the chromatic index of Gand is denoted by χ(G). A proper edge coloring c is called acyclic if there are no bichromatic cycles in the graph. In other words an edge coloring is acyclic if the union of any two color classes induces a set of paths (i.e., linear forest) in G. The acyclic edge chromatic number (also called acyclic chromatic index), denoted by a’(G), is the minimum

APA, Harvard, Vancouver, ISO, and other styles

24

Basavaraju, Manu. "Acyclic Edge Coloring Of Graphs." Thesis, 2010. http://etd.iisc.ernet.in/handle/2005/2263.

Full text

Abstract:

A proper edge coloring of G =(V,E)is a map c : E → C (where C is the set of available colors ) with c(e) ≠ c(ƒ) for any adjacent edges e,f. The minimum number of colors needed to properly color the edges of G, is called the chromatic index of Gand is denoted by χ(G). A proper edge coloring c is called acyclic if there are no bichromatic cycles in the graph. In other words an edge coloring is acyclic if the union of any two color classes induces a set of paths (i.e., linear forest) in G. The acyclic edge chromatic number (also called acyclic chromatic index), denoted by a’(G), is the minimum

APA, Harvard, Vancouver, ISO, and other styles

25

"Coloring Graphs from Almost Maximum Degree Sized Palettes." Doctoral diss., 2013. http://hdl.handle.net/2286/R.I.17753.

Full text

Abstract:

abstract: Every graph can be colored with one more color than its maximum degree. A well-known theorem of Brooks gives the precise conditions under which a graph can be colored with maximum degree colors. It is natural to ask for the required conditions on a graph to color with one less color than the maximum degree; in 1977 Borodin and Kostochka conjectured a solution for graphs with maximum degree at least 9: as long as the graph doesn't contain a maximum-degree-sized clique, it can be colored with one fewer than the maximum degree colors. This study attacks the conjecture on multiple fronts

APA, Harvard, Vancouver, ISO, and other styles

26

Lahiri, Abhiruk. "Problems on bend-number, circular separation dimension and maximum edge 2-colouring." Thesis, 2018. https://etd.iisc.ac.in/handle/2005/5491.

Full text

Abstract:

Representation of graphs as the intersection graphs of geometric objects has a long history. The objective is to a nd a collection of \simple" sets S such that a given graph G is its intersection graph. We are interested in two types of intersection representations motivated by VLSI circuit layout problem. In these models, vertices are represented by polygonal paths with alternating horizontal and vertical segments. The measure of the complexity of a path is de fined by the number of bends it has. The objective is to minimise the maximum number of bends used by any path in a representat

APA, Harvard, Vancouver, ISO, and other styles

27

Volec, Jan. "Vlastnosti grafů velkého obvodu." Master's thesis, 2011. http://www.nusl.cz/ntk/nusl-313777.

Full text

Abstract:

In this work we study two random procedures in cubic graphs with large girth. The first procedure finds a probability distribution on edge-cuts such that each edge is in a randomly chosen cut with probability at least 0.88672. As corollaries, we derive lower bounds for the size of maximum cut in cubic graphs with large girth and in random cubic graphs, and also an upper bound for the fractional cut covering number in cubic graphs with large girth. The second procedure finds a probability distribution on independent sets such that each vertex is in an independent set with probability at least 0

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!