To see the other types of publications on this topic, follow the link: Coloring graphs.
Dissertations / Theses on the topic 'Coloring graphs'
Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles
Consult the top 50 dissertations / theses for your research on the topic '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
Le, Ngoc Khang. "Detecting and Coloring some Graph Classes." Thesis, Lyon, 2018. http://www.theses.fr/2018LYSEN021/document.
Full textAbstract:
Les graphes sont des structures mathématiques utilisées pour modéliser les relations par paires entre objets. Malgré leur structure simple, les graphes ont des applications dans divers domaines tels que l'informatique, la physique, la biologie et la sociologie. L'objectif principal de ce travail est de continuer l'étude des problèmes de coloration et de détection dans le cadre de classes de graphes fermées par sous-graphes induits (que nous appelons classes de graphes héréditaires).La première classe que nous considérons est graphes sans ISK4 - les graphes qui ne contiennent aucune subdivision de en tant que sous-graphe induit. Nous montrons que le nombre chromatique de cette classe est limité à 24, une amélioration considérable par rapport à la borne existant précédemment. Nous donnons également une bien meilleure limite dans le cas sans triangle. De plus, nous prouvons qu'il existe un algorithme de complexité pour détecter cette classe, ce qui répond à une question de Chudnovsky et al. et Lévêque et al.La deuxième classe que nous étudions est celle des graphes sans trou pair et sans étoile d’articulation. Cela est motivé par l'utilisation de la technique de décomposition pour résoudre certains problèmes d'optimisation. Nous garantissons la fonction χ-bounding optimale pour cette classe. Nous montrons que la classe a rank-width bornée, ce qui implique l'existence d'un algorithme de coloration en temps polynomial. Enfin, la coloration gloutonne connexe dans les graphes sans griffes est considérée. Une façon naturelle de colorier un graphe est d'avoir un ordre de ses sommets et d'affecter pour chaque sommet la première couleur disponible. Beaucoup de recherches ont été faites pour des ordres généraux. Cependant, nous connaissons très peu de choses sur la caractérisation des bons graphes par rapport aux ordres connexes. Un graphe est bon si pour chaque sous-graphe induit connexe de , chaque ordre connexe donne à une coloration optimale. Nous donnons la caractérisation complète de bons graphes sans griffes en termes de sous-graphes induits minimaux interditsGraphs are mathematical structures used to model pairwise relations between objects. Despite their simple structures, graphs have applications in various areas like computer science, physics, biology and sociology. The main focus of this work is to continue the study of the coloring and detecting problems in the setting of graph classes closed under taking induced subgraphs (which we call hereditary graph classes). The first class we consider is ISK4-free graphs - the graphs that do not contain any subdivision of K4 as an induced subgraph. We prove that the chromatic number of this class is bounded by 24, a huge improvement compared to the best-known bound. We also give a much better bound in the triangle-free case. Furthermore, we prove that there exists an O(n 9) algorithm for detecting this class, which answers a question by Chudnovsky et al. and Lévêque et al. The second class we study is even-hole-free graphs with no star cutset. This was motivated by the use of decomposition technique in solving some optimization problems. We prove the optimal χ -bounding function for this class and show that it has bounded rank-width, which implies the existence of a polynomial-time coloring algorithm.Finally, the connected greedy coloring in claw-free graphs is considered. A natural way to color a graph is to have an order of its vertices and assign for each vertex the first available color. A lot of researches have been done for general orders. However, we know very little about the characterization of good graphs with respect to connected orders. A graph G is good if for every connected induced subgraph H of G, every connected order gives H an optimal coloring. We give the complete characterization of good claw-free graphs in terms of minimal forbidden induced subgraphs
2
Montgomery, Bruce Lee. "Dynamic coloring of graphs." Morgantown, W. Va. : [West Virginia University Libraries], 2001. http://etd.wvu.edu/templates/showETD.cfm?recnum=2109.
Full textAbstract:
Thesis (Ph. D.)--West Virginia University, 2001.Title from document title page. Document formatted into pages; contains viii, 52 p. : ill. Vita. Includes abstract. Includes bibliographical references (p. 51).
3
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 textAbstract:
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 colors required for a gap vertex-distinguishing edgecoloring of G is called the gap chromatic number of G and is denoted by gap(G).We will compute this parameter for a large set of graphs G of order n and we evenprove that gap(G) 2 fn E 1; n; n + 1g.In the second part, we focus on graph packing problems, which is an area ofgraph theory that has grown significantly over the past several years. However, themajority of existing works focuses on unlabeled graphs. In this thesis, we introducefor the first time the packing problem for a vertex labeled graph. Roughly speaking,it consists of graph packing which preserves the labels of the vertices. We studythe corresponding optimization parameter on several classes of graphs, as well asfinding general bounds and characterizations.The last part deal with the query processing of a core subset of XML query languages:XML twig queries. An XML twig query, represented as a small query tree,is essentially a complex selection on the structure of an XML document. Matching atwig query means finding all the occurrences of the query tree embedded in the XMLdata tree. Many holistic twig join algorithms have been proposed to match XMLtwig pattern. Most of these algorithms find twig pattern matching in two steps. Inthe first one, a query tree is decomposed into smaller pieces, and solutions againstthese pieces are found. In the second step, all of these partial solutions are joinedtogether to generate the final solutions. In this part, we propose a novel holistictwig join algorithm, called TwigStack++, which features two main improvementsin the decomposition and matching phase. The proposed solutions are shown to beefficient and scalable, and should be helpful for the future research on efficient queryprocessing in a large XML database.
4
Yerger, Carl Roger Jr. "Color-critical graphs on surfaces." Diss., Georgia Institute of Technology, 2010. http://hdl.handle.net/1853/37197.
Full textAbstract:
A graph is (t+1)-critical if it is not t-colorable, but every proper subgraph is. In this thesis, we study the structure of critical graphs on higher surfaces. One major result in this area is Carsten Thomassen's proof that there are finitely many 6-critical graphs on a fixed surface. This proof involves a structural theorem about a precolored cycle C of length q. In general terms, he proves that a coloring, c, of C, can be extended inside the cycle, or there exists a subgraph H with at most a number of vertices exponential in q such that c can not be extended to a 5-coloring of H. In Chapter 2, we proved an alternative proof that reduces the number of vertices in H to be cubic in q. In Chapter 3, we find the nine 6-critical graphs among all graphs embeddable on the Klein bottle. In Chapter 4, we prove a result concerning critical graphs related to an analogue of Steinberg's conjecture for higher surfaces. We show that if G is a 4-critical graph embedded on surface S, with Euler genus g and has no cycles of length four through ten, then G has at most 2442g + 37 vertices.
5
Fowler, Thomas George. "Unique coloring of planar graphs." Diss., Georgia Institute of Technology, 1998. http://hdl.handle.net/1853/30358.
Full text
6
Salavatipour, Mohammadreza. "On sum coloring of graphs." Thesis, National Library of Canada = Bibliothèque nationale du Canada, 2000. http://www.collectionscanada.ca/obj/s4/f2/dsk1/tape3/PQDD_0023/MQ50369.pdf.
Full text
7
Sengupta, Rik. "List coloring in general graphs." Thesis, Massachusetts Institute of Technology, 2015. http://hdl.handle.net/1721.1/112878.
Full textAbstract:
Thesis: S.M., Massachusetts Institute of Technology, Department of Mathematics, 2015.Cataloged from PDF version of thesis.
Includes bibliographical references (pages 30-31).
In this thesis we explore some of the relatively new approaches to the problem of list-coloring graphs. This is a problem that has its roots in classical graph theory, but has developed an entire theory of its own, that uses tools from structural graph theory, probabilistic approaches, as well as heuristic and algorithmic approaches. This thesis details two approaches one can take to understand list-coloring and prove results for several classes of graphs; one of them is to use the idea of graph kernels, and the other is to look at list-edge-coloring. In this thesis we present the state-of-the-art research on these two problems. We begin by setting up definitions and preliminaries, and then go into each of these two topics in turn. Along the way we briefly mention some of the very new research on the topics, including some new approaches developed for the purpose of writing this thesis. We finish with a survey of some of the major open problems that still remain in the area.
by Rik Sengupta.
S.M.
8
Kurt, Oguz. "On The Coloring of Graphs." The Ohio State University, 2009. http://rave.ohiolink.edu/etdc/view?acc_num=osu1262287401.
Full text
9
Song, Zengmin. "Cycles and coloring in graphs." HKBU Institutional Repository, 2001. http://repository.hkbu.edu.hk/etd_ra/285.
Full text
10
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 textAbstract:
Thesis (M. S.)--Computing, Georgia Institute of Technology, 2009.Committee Chair: Prof. Richard Lipton; Committee Member: Prof. Dana Randall; Committee Member: Prof. H. Venkateswaran. Part of the SMARTech Electronic Thesis and Dissertation Collection.
11
Roussel, Nicolas. "Circular coloring and acyclic choosability of graphs." Thesis, Bordeaux 1, 2009. http://www.theses.fr/2009BOR13889/document.
Full textAbstract:
Dans cette thèse, nous nous intéressons à la coloration circulaire des graphes planaires. Des bornes supérieures ont été données pour des graphes avec degré maximum borné, avec girth, la longueur de son plus petit cycle, bornée, avec des cycles manquants, etc. Ici nous donnerons de nouvelles bornes pour les graphes avec degré moyen maximum borné. Nous étudions également la coloration totale et la coloration (d,1)-totale de plusieurs familles infinies de graphes. Nous décrivons le nouveau concept de coloration (d,1)-totale circulaire. Enfin, nous discutons les conditions nécessaires pour qu'un graphe planaire admette une coloration acyclique par listes de taille 4In this thesis, we study the circular coloring of planar graphs. Upper bounds have been given for graphs with bounded maximum degree, with bounded girth, that is the length of its smallest cycle, with missing cycles, and so on. It has also been studied for graphs with bounded maximum average degree. Here we give new upper bounds for that latter case. We also study the total coloring and ($d,1$)-total labeling of a few infinite families of graphs and describe the new concept of circular ($d,1$)-total labeling of graphs. In the last part, we will discuss conditions for a planar graph to be acyclically $4$-choosable
12
Postle, Luke Jamison. "5-list-coloring graphs on surfaces." Diss., Georgia Institute of Technology, 2012. http://hdl.handle.net/1853/45807.
Full textAbstract:
Thomassen proved that there are only finitely many 6-critical graphs embeddable on a fixed surface. He also showed that planar graphs are 5-list-colorable. This thesis develops new techniques to prove general theorems for 5-list-coloring graphs embedded in a fixed surface. Indeed, a general paradigm is established which improves a number of previous results while resolving several open conjectures. In addition, the proofs are almost entirely self-contained.
In what follows, let S be a fixed surface, G be a graph embedded in S and L a list assignment such that, for every vertex v of G, L(v) has size at least five. First, the thesis provides an independent proof of a theorem of DeVos, Kawarabayashi and Mohar that says if G has large edge-width, then G is 5-list-colorable. Moreover, the bound on the edge-width is improved from exponential to logarithmic in the Euler genus of S, which is best possible up to a multiplicative constant. Second, the thesis proves that there exist only finitely many 6-list-critical graphs embeddable in S, solving a conjecture of Thomassen from 1994. Indeed, it is shown that the number of vertices in a 6-list-critical graph is at most linear in genus, which is best possible up to a multiplicative constant. As a corollary, there exists a linear-time algorithm for deciding 5-list-colorability of graphs embeddable in S.
Furthermore, we prove that the number of L-colorings of an L-colorable graph embedded in S is exponential in the number of vertices of G, with a constant depending only on the Euler genus g of S. This resolves yet another conjecture of Thomassen from 2007. The thesis also proves that if X is a subset of the vertices of G that are pairwise distance Omega(log g) apart and the edge-width of G is Omega(log g), then any L-coloring of X extends to an L-coloring of G. For planar graphs, this was conjectured by Albertson and recently proved by Dvorak, Lidicky, Mohar, and Postle. For regular coloring, this was proved by Albertson and Hutchinson. Other related generalizations are examined.
13
Walls, Barrett Hamilton. "Coloring girth restricted graphs on surfaces." Diss., Georgia Institute of Technology, 1999. http://hdl.handle.net/1853/28939.
Full text
14
Li, Ching-man. "Various coloring problems on plane graphs." Click to view the E-thesis via HKUTO, 2007. http://sunzi.lib.hku.hk/hkuto/record/B39006542.
Full text
15
Li, Ching-man, and 李靜文. "Various coloring problems on plane graphs." Thesis, The University of Hong Kong (Pokfulam, Hong Kong), 2007. http://hub.hku.hk/bib/B39006542.
Full text
16
Kang, Yingli [Verfasser]. "Coloring of signed graphs / Yingli Kang." Paderborn : Universitätsbibliothek, 2018. http://d-nb.info/1153824663/34.
Full text
17
Djang, Claire. "Two-Coloring Cycles In Complete Graphs." Oberlin College Honors Theses / OhioLINK, 2013. http://rave.ohiolink.edu/etdc/view?acc_num=oberlin1370618319.
Full text
18
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 textAbstract:
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 creation of arbitrarily large graphs of the discussed class is provided, and a polynomial-time algorithm for recognizing graphs in the class is given. Several invariants for the class are discussed. The edge-face chromatic number χef of a plane graph G is the minimum number of colors that must be assigned to the edges and faces of G such that no edge or face of G receives the same color as an edge or face with which it is incident or adjacent. A well-known result for the upper bound of χef exists for graphs with maximum degree Δ ≥ 10. We present a tight upper bound for plane graphs with Δ = 9.Ph.D.
Department of Mathematics
Sciences
Mathematics PhD
19
Chen, Min. "Vertex coloring of graphs via the discharging method." Thesis, Bordeaux 1, 2010. http://www.theses.fr/2010BOR14090/document.
Full textAbstract:
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ésultats impliquent plusieurs résultats connus.La notion de la coloration acyclique par liste des graphes planaires a été introduite par Borodin, Fon-Der Flaass, Kostochka, Raspaud, et Sopena. Ils ont conjecturé que tout graphe planaire est acycliquement 5-liste coloriable. Dans le Chapitre 3, on obtient des conditions suffisantes pour qu’un graphe planaire admette une k-coloration acyclique par liste avec k 2 f3; 4; 5g.Dans le Chapitre 4, nous montrons que tout graphe subcubique est 6-étoilé coloriable.D’autre part, Fertin, Raspaud et Reed ont montré que le graphe de Wagner ne peut pas être 5-étoilé-coloriable. Ce fait implique que notre résultat est optimal. De plus, nous obtenons des nouvelles bornes supérieures sur la choisissabilité étoilé d’un graphe planaire subcubique de maille donnée.Une k-forêt-coloration d’un graphe G est une application ¼ de l’ensemble des sommets V (G) de G dans l’ensemble de couleurs 1; 2; ¢ ¢ ¢ ; k telle que chaque classede couleur induit une forêt. Le sommet-arboricité de G est le plus petit entier ktel que G a k-forêt-coloration. Dans le Chapitre 5, nous prouvons une conjecture de Raspaud et Wang affirmant que tout graphe planaire sans triangles intersectants admet une sommet-arboricité au plus 2.Enfin, au Chapitre 6, nous nous concentrons sur le problème d’homomorphisme des graphes peu denses dans le graphe de Petersen. Plus précisément, nous prouvons que tout graphe sans triangles ayant un degré moyen maximum moins de 5=2 admet un homomorphisme dans le graphe de Petersen. En outre, nous montrons que la borne sur le degré moyen maximum est la meilleure possibleIn this thesis, we are interested in various vertex coloring and homomorphism problems of graphs with special emphasis on planar graphs and sparsegraphs. We consider proper vertex coloring, acyclic coloring, star coloring, forestcoloring, fractional coloring and the list version of most of these concepts.In Chapter 2, we consider the problem of finding sufficient conditions for a planargraph to be 3-choosable. These conditions are expressed in terms of forbiddensubgraphs and our results extend several known results.The notion of acyclic list coloring of planar graphs was introduced by Borodin,Fon-Der Flaass, Kostochka, Raspaud, and Sopena. They conjectured that everyplanar graph is acyclically 5-choosable. In Chapter 3, we obtain some sufficientconditions for planar graphs to be acyclically k-choosable with k 2 f3; 4; 5g.In Chapter 4, we prove that every subcubic graph is 6-star-colorable. On theother hand, Fertin, Raspaud and Reed showed that the Wagner graph cannot be5-star-colorable. This fact implies that our result is best possible. Moreover, weobtain new upper bounds on star choosability of planar subcubic graphs with givengirth.A k-forest-coloring of a graph G is a mapping ¼ from V (G) to the set f1; ¢ ¢ ¢ ; kgsuch that each color class induces a forest. The vertex-arboricity of G is the smallestinteger k such that G has a k-forest-coloring. In Chapter 5, we prove a conjecture ofRaspaud and Wang asserting that every planar graph without intersecting triangleshas vertex-arboricity at most 2.Finally, in Chapter 6, we focus on the homomorphism problems of sparse graphsto the Petersen graph. More precisely, we prove that every triangle-free graph withmaximum average degree less than 5=2 admits a homomorphism to the Petersengraph. Moreover, we show that the bound on the maximum average degree in ourresult is best possible
20
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
21
Adams, Sarah E. "Chromatic Polynomials for Graphs with Split Vertices." Bowling Green State University / OhioLINK, 2020. http://rave.ohiolink.edu/etdc/view?acc_num=bgsu1593819941367146.
Full text
22
Chan, Wai Hong. "The bandwidth and coloring problems of graphs." HKBU Institutional Repository, 2003. http://repository.hkbu.edu.hk/etd_ra/472.
Full text
23
Bonamy, Marthe. "Global discharging methods for coloring problems in graphs." Thesis, Montpellier, 2015. http://www.theses.fr/2015MONTS261.
Full textAbstract:
Cette thèse s'inscrit dans le cadre de la théorie des graphes, et porte plus particulièrement sur des problèmes de coloration de graphes. Dans cette thèse, nous nous intéressons à l'utilisation et au développement de la méthode de déchargement, un argument de comptage qui exploite fortement la structure du graphe. Cette méthode est décisive dans la preuve du Théorème des Quatre Couleurs. Nous donnons d'abord une vue d'ensemble des outils de déchargement que nous utilisons dans ce travail, entre les méthodes élégantes mises en application, et les astuces développées. Dans le cadre de la coloration d'arêtes par liste, nous résolvons la Conjecture de Coloration par Liste faible dans le cas des graphes planaires de degré maximum 8, en prouvant qu'on peut colorier par liste les arêtes de ces derniers avec 9 couleurs seulement. Ceci améliore un résultat de Borodin de 1990. Enfin, nous présentons nos résultats dans le cadre de la coloration de carrés, où il s'agit de colorier les sommets sans qu'il y ait deux sommets adjacents ou avec un voisin commun qui soient de la même couleur. On s'intéresse en particulier à des conditions suffisantes sur la densité du graphe (c-à-d le degré moyen maximum d'un sous-graphe) pour qu'on puisse colorier son carré avec peu de couleursThis thesis falls within graph theory, and deals more precisely with graph coloring problems. In this thesis, we use and develop the discharging method, a counting argument that makes strong advantage of the graph structure. This method is decisive in the proof of the Four Color Theorem. We first give an illustrated overview of the discharging tools that are used for this work: nice methods that we apply, and handy tricks that we develop. In the realm of list edge coloring, we most notably prove that the weak List Coloring Conjecture is true for planar graphs of maximum degree 8 (i.e. that they are edge 9-choosable), thus improving over a result of Borodin from 1990. We finally present our results about square coloring, where the goal is to color the vertices in such a way that two vertices that are adjacent or have a common neighbor receive different colors. We look in particular into sufficient conditions on the density of a graph (i.e. the maximum average degree of a subgraph) for its square to be colorable with few colo
24
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
25
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 textAbstract:
PONTIFÍCIA UNIVERSIDADE CATÓLICA DO RIO DE JANEIROCONSELHO NACIONAL DE DESENVOLVIMENTO CIENTÍFICO E TECNOLÓGICO
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 número cromático total de um grafo é o menor inteiro positivo para o qual o grafo possui coloração total. Dada uma coloração total, se a diferença entre as cardinalidades de quaisquer duas classes de cor for no máximo um, então dizemos que a coloração é equilibrada e o menor número inteiro positivo que satisfaz essa condição é dito o número cromático total equilibrado do grafo. Para tal valor, Wang (2002) conjecturou um limite superior. Um grafo multipartido completo balanceado é aquele em que o conjunto de vértices pode ser particionado em conjuntos independentes com a mesma quantidade de vértices, sendo adjacentes quaisquer dois vértices de diferentes partes da partição. Determinamos o número cromático total equilibrado dos grafos multipartidos completos balanceados, contribuindo, desta forma, com novos resultados na área de coloração de grafos.
An edge coloring is the assignment of colors to the edges of a graph, so that adjacent edges do not receive the same color. The smallest positive integer for which a graph admits an edge coloring is said to be its chromatic index. We did a literature review of the main known results of this area. A total coloring, in turn, is the application of colors to the vertices and edges of a graph so that adjacent or incident elements receive distinct colors. The total chromatic number of a graph is the least positive integer for which the graph has a total coloring.Given a total coloring, if the difference between the cardinality of any two color classes is at most one, then we say that the coloring is equitable and the smallest positive integer that satisfies this condition is said to be the graph s equitable total chromatic number. For such value, Wang (2002) conjectured an upper bound. A complete multipartite balanced graph is the one in which the set of vertices can be partitioned into independent sets with the same quantity of vertices, being adjacent any two vertices of different parts of the partition. We determine the equitable total chromatic number of complete multipartite graphs, contributing, therefore, with new results in the area of graph coloring.
26
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 textAbstract:
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 of X and Y, where all the vertices in X only have neighbors in Y and vice versa. A bipartite graph is a graph whose vertices admit a bipartition (X,Y). Let G be one such graph. An X-interval coloring of G is a proper edge coloring where the colors of the edges incident to each vertex in X form an interval of integers. Denote by χ'int(G,X) the least number of colors needed for an X-interval coloring of G. In this paper we prove that if G is a bipartite graph with maximum degree 3n (n is a natural number), where all the vertices in X have degree 3, then
27
Harney, Isaiah H. "Colorings of Hamming-Distance Graphs." UKnowledge, 2017. http://uknowledge.uky.edu/math_etds/49.
Full textAbstract:
Hamming-distance graphs arise naturally in the study of error-correcting codes and have been utilized by several authors to provide new proofs for (and in some cases improve) known bounds on the size of block codes. We study various standard graph properties of the Hamming-distance graphs with special emphasis placed on the chromatic number. A notion of robustness is defined for colorings of these graphs based on the tolerance of swapping colors along an edge without destroying the properness of the coloring, and a complete characterization of the maximally robust colorings is given for certain parameters. Additionally, explorations are made into subgraph structures whose identification may be useful in determining the chromatic number.
28
Baber, Courtney Leigh. "An Introduction to List Colorings of Graphs." Thesis, Virginia Tech, 2009. http://hdl.handle.net/10919/33484.
Full textAbstract:
One of the most popular and useful areas of graph theory is graph colorings. A graph
coloring is an assignment of integers to the vertices of a graph so that no two adjacent
vertices are assigned the same integer. This problem frequently arises in scheduling and
channel assignment applications. A list coloring of a graph is an assignment of integers
to the vertices of a graph as before with the restriction that the integers must come from
specific lists of available colors at each vertex. For a physical application of this problem,
consider a wireless network. Due to hardware restrictions, each radio has a limited set of
frequencies through which it can communicate, and radios within a certain distance of each
other cannot operate on the same frequency without interfering. We model this problem as
a graph by representing the wireless radios by vertices and assigning a list to each vertex
according to its available frequencies. We then seek a coloring of the graph from these lists.
In this thesis, we give an overview of the last thirty years of research in list colorings. We
begin with an introduction of the list coloring problem, as defined by ErdË os, Rubin, and
Taylor in [6]. We continue with a study of variations of the problem, including cases when
all the lists have the same length and cases when we allow different lengths. We will briefly
mention edge colorings and overview some restricted list colors such as game colorings and
L(p, q)-labelings before concluding with a list of open questions.Master of Science
29
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
30
Seregi, Benjámin. "On the list coloring of k-band buffering cellular graphs." Thesis, KTH, Skolan för elektroteknik och datavetenskap (EECS), 2018. http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-254888.
Full textAbstract:
The optimal channel allocation problem in cellular networks is often formulated in a graph theoretic framework. One of its variants–where each access point knows the list of its free channels–is related the so-called list coloring problem and is closely related to the channel allocation of IEEE 802.11 systems. In spite of the fact that the list coloring problem is NP-complete for arbitrary graphs, we show that there exists a polynomial time algorithm that k-list colors an arbitrary graph where k is the Szekeres–Wilf number of the graph. In addition, an upper bound for the choice number of k-band buffering cellular graphs is obtained proving that they are (3k(k + 1)/2 + 1)-choosable. A Java application is implemented to compute the Szekeres–Wilf number of generated cellular graph in order to facilitate making further conjectures of sharper upper bounds for the choice number.Det optimala kanalallokeringsproblemet i mobilnät formuleras ofta i en grafteoretisk ram. En av dess varianter, där varje accesspunkt känner till listan av fria kanaler–är relaterad till det så kallade listfärgningsproblemet och är nära besläktat med kanaltilldelningen i IEEE 802.11-system. Trots det faktum att listfärgningsproblemet är NP-komplett för godtyckliga grafer, visar vi att det finns en algoritm med en komplexitet i polynom tid som k-lista färgar en godtycklig graf där k är Szekeres-Wilf-numret av grafen. Dessutom erhålls en övre gräns (3k(k +1)/2+1), för valet av antal k-band buffrande cellulära grafer.En Java-applikation är implementerad för att beräkna Szekeres–Wilf-numret av genererade cellulär graf för att underlätta fortsatt arbete med att ytterligare finna skarpare övre gränser för valnumret.
31
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
32
Duffy, Christopher. "Homomorphisms of (j, k)-mixed graphs." Thesis, Bordeaux, 2015. http://hdl.handle.net/1828/6601.
Full textAbstract:
A mixed graph is a simple graph in which a subset of the edges have been assigned directions to form arcs. For non-negative integers j and k, a (j, k)−mixed graph is a mixed graph with j types of arcs and k types of edges. The collection of (j, k)−mixed graphs contains simple graphs ((0,1)−mixed graphs), oriented graphs ((1,0)-mixed graphs) and k−edge-coloured graphs ((0, k)−mixed graphs).
A homomorphism is a vertex mapping from one (j,k)−mixed graph to another in which edge type is preserved, and arc type and direction are preserved. An m−colouring of a (j, k)−mixed graph is a homomorphism from that graph to a target with m vertices. The (j, k)−chromatic number of a (j, k)−mixed graph is the least m such that an m−colouring exists. When (j, k) = (0, 1), we see that these definitions are consistent with the usual definitions of graph homomorphism and graph colouring. Similarly, when (j, k) = (1, 0) and (j, k) = (0, k) these definitions are consistent with the usual definitions of homomorphism and colouring for oriented graphs and k−edge-coloured graphs, respectively.
In this thesis we study the (j, k)−chromatic number and related parameters for different families of graphs, focussing particularly on the (1, 0)−chromatic number, more commonly called the oriented chromatic number, and the (0, k)−chromatic number.
In examining oriented graphs, we provide improvements to the upper and lower bounds for the oriented chromatic number of the families of oriented graphs with maximum degree 3 and 4. We generalise the work of Sherk and MacGillivray on the 2−dipath chromatic number, to consider colourings in which vertices at the ends of
iii
a directed path of length at most k must receive different colours. We examine the implications of the work of Smolikova on simple colourings to study of the oriented chromatic number of the family of oriented planar graphs.
In examining k−edge-coloured graphs we provide improvements to the upper and lower bounds for the family of 2−edge-coloured graphs with maximum degree 3. In doing so, we define the alternating 2−path chromatic number of k−edge-coloured graphs, a parameter similar in spirit to the 2−dipath chromatic number for oriented graphs. We also consider a notion of simple colouring for k−edge-coloured graphs, and show that the methods employed by Smolikova ́ for simple colourings of oriented graphs may be adapted to k−edge-coloured graphs.
In addition to considering vertex colourings, we also consider incidence colourings of both graphs and digraphs. Using systems of distinct representatives, we provide a new characterisation of the incidence chromatic number. We define the oriented incidence chromatic number and find, by way of digraph homomorphism, a connection between the oriented incidence chromatic number and the chromatic number of the underlying graph. This connection motivates our study of the oriented incidence chromatic number of symmetric complete digraphs.Graduate
33
Bosse, Ruth. "On Minimal Non-(2, 1)-Colorable Graphs." Thesis, Stockholms universitet, Matematiska institutionen, 2017. http://urn.kb.se/resolve?urn=urn:nbn:se:su:diva-143532.
Full textAbstract:
A graph is (2, 1)-colorable if it allows a partition of its vertices into two classes such that both induce graphs with maximum degree at most one. A non-(2, 1)-colorable graph is minimal if all proper subgraphs are (2, 1)-colorable. We prove that such graphs are 2-edge-connected and that every edge sits in an odd cycle. Furthermore, we show properties of edge cuts and particular graphs which are no induced subgraphs. We demonstrate that there are infinitely many minimal non-(2, 1)-colorable graphs, at least one of order n for all n ≥ 5. Moreover, we present all minimal non-(2, 1)- colorable graphs of order at most seven. We consider the maximum degree of minimal non-(2, 1)-colorable graphs and show that it is at least four but can be arbitrarily large. We prove that the average degree is greater than 8/3 and give sufficient properties for graphs with average degree greater than 14/5. We conjecture that all minimal non-(2, 1)-colorable graphs fulfill these properties.
34
Hall, Coleman. "On List-Coloring and the Sum List Chromatic Number of Graphs." VCU Scholars Compass, 2011. http://scholarscompass.vcu.edu/etd/2393.
Full textAbstract:
This thesis explores several of the major results in list-coloring in an expository fashion. As a specialization of list coloring, the sum list chromatic number is explored in detail. Ultimately, the thesis is designed to motivate the discussion of coloring problems and, hopefully, interest the reader in the branch of coloring problems in graph theory.
35
Serrato, Alexa. "Reed's Conjecture and Cycle-Power Graphs." Scholarship @ Claremont, 2014. http://scholarship.claremont.edu/hmc_theses/59.
Full textAbstract:
Reed's conjecture is a proposed upper bound for the chromatic number of a graph. Reed's conjecture has already been proven for several families of graphs. In this paper, I show how one of those families of graphs can be extended to include additional graphs and also show that Reed's conjecture holds for a family of graphs known as cycle-power graphs, and also for their complements.
36
Zacharopoulos, Panagiotis [Verfasser]. "Asymmetric game perfect graphs and the circular coloring game of weighted graphs / Panagiotis Zacharopoulos. Fakultät für Mathematik." Bielefeld : Universitätsbibliothek Bielefeld, Hochschulschriften, 2012. http://d-nb.info/1024640639/34.
Full text
37
Mortada, Maidoun. "The b-chromatic number of regular graphs." Thesis, Lyon 1, 2013. http://www.theses.fr/2013LYO10116.
Full textAbstract:
Les deux problèmes majeurs considérés dans cette thèse : le b-coloration problème et le graphe emballage problème. 1. Le b-coloration problème : Une coloration des sommets de G s'appelle une b-coloration si chaque classe de couleur contient au moins un sommet qui a un voisin dans toutes les autres classes de couleur. Le nombre b-chromatique b(G) de G est le plus grand entier k pour lequel G a une b-coloration avec k couleurs. EL Sahili et Kouider demandent s'il est vrai que chaque graphe d-régulier G avec le périmètre au moins 5 satisfait b(G) = d + 1. Blidia, Maffray et Zemir ont montré que la conjecture d'El Sahili et de Kouider est vraie pour d ≤ 6. En outre, la question a été résolue pour les graphes d-réguliers dans des conditions supplémentaires. Nous étudions la conjecture d'El Sahili et de Kouider en déterminant quand elle est possible et dans quelles conditions supplémentaires elle est vrai. Nous montrons que b(G) = d + 1 si G est un graphe d-régulier qui ne contient pas un cycle d'ordre 4 ni d'ordre 6. En outre, nous fournissons des conditions sur les sommets d'un graphe d-régulier G sans le cycle d'ordre 4 de sorte que b(G) = d + 1. Cabello et Jakovac ont prouvé si v(G) ≥ 2d3 - d2 + d, puis b(G) = d + 1, où G est un graphe d-régulier. Nous améliorons ce résultat en montrant que si v(G) ≥ 2d3 - 2d2 + 2d alors b(G) = d + 1 pour un graphe d-régulier G. 2. Emballage de graphe problème : Soit G un graphe d'ordre n. Considérer une permutation σ : V (G) → V (Kn), la fonction σ* : E(G) → E(Kn) telle que σ *(xy) = σ *(x) σ *(y) est la fonction induite par σ. Nous disons qu'il y a un emballage de k copies de G (dans le graphe complet Kn) s'il existe k permutations σi : V (G) → V (Kn), où i = 1, …, k, telles que σi*(E(G)) ∩ σj (E(G)) = ɸ pour i ≠ j. Un emballage de k copies d'un graphe G est appelé un k-placement de G. La puissance k d'un graphe G, noté par Gk, est un graphe avec le même ensemble de sommets que G et une arête entre deux sommets si et seulement si le distance entre ces deux sommets est au plus k. Kheddouci et al. ont prouvé que pour un arbre non-étoile T, il existe un 2-placement σ sur V (T). Nous introduisons pour la première fois le problème emballage marqué de graphe dans son graphe puissanceTwo problems are considered in this thesis: the b-coloring problem and the graph packing problem. 1. The b-Coloring Problem : A b-coloring of a graph G is a proper coloring of the vertices of G such that there exists a vertex in each color class joined to at least a vertex in each other color class. The b-chromatic number of a graph G, denoted by b(G), is the maximum number t such that G admits a b-coloring with t colors. El Sahili and Kouider asked whether it is true that every d-regular graph G with girth at least 5 satisfies b(G) = d + 1. Blidia, Maffray and Zemir proved that the conjecture is true for d ≤ 6. Also, the question was solved for d-regular graphs with supplementary conditions. We study El Sahili and Kouider conjecture by determining when it is possible and under what supplementary conditions it is true. We prove that b(G) = d+1 if G is a d-regular graph containing neither a cycle of order 4 nor of order 6. Then, we provide specific conditions on the vertices of a d-regular graph G with no cycle of order 4 so that b(G) = d + 1. Cabello and Jakovac proved that if v(G) ≥ 2d3 - d2 + d, then b(G) = d + 1, where G is a d-regular graph. We improve this bound by proving that if v(G) ≥ 2d3 - 2d2 + 2d, then b(G) = d+1 for a d-regular graph G. 2. Graph Packing Problem : Graph packing problem is a classical problem in graph theory and has been extensively studied since the early 70's. Consider a permutation σ : V (G) → V (Kn), the function σ* : E(G) → E(Kn) such that σ *(xy) = σ *(x) σ *(y) is the function induced by σ. We say that there is a packing of k copies of G into the complete graph Kn if there exist k permutations σ i : V (G) → V (Kn), where i = 1,…, k, such that σ*i (E(G)) ∩ σ*j (E(G)) = ɸ for I ≠ j. A packing of k copies of a graph G will be called a k-placement of G. The kth power Gk of a graph G is the supergraph of G formed by adding an edge between all pairs of vertices of G with distance at most k. Kheddouci et al. proved that for any non-star tree T there exists a 2-placement σ on V (T). We introduce a new variant of graph packing problem, called the labeled packing of a graph into its power graph
38
Loeb, Sarah. "Extending List Colorings of Planar Graphs." Scholarship @ Claremont, 2011. http://scholarship.claremont.edu/hmc_theses/6.
Full textAbstract:
In the study of list colorings of graphs, we assume each vertex of a graph has a specified list of colors from which it may be colored. For planar graphs, it is known that there is a coloring for any list assignment where each list contains five colors. If we have some vertices that are precolored, can we extend this to a coloring of the entire graph? We explore distance constraints when we allow the lists to contain an extra color. For lists of length five, we fix $W$ as a subset of $V(G)$ such that all vertices in $W$ have been assigned colors from their respective lists. We give a new, simplified proof where there are a small number of precolored vertices on the same face. We also explore cases where $W=\{u,v\}$ and $G$ has a separating $C_3$ or $C_4$ between $u$ and $v$.
39
Jaeger, Robert. "Coloring the Square of Planar Graphs Without 4-Cycles or 5-Cycles." VCU Scholars Compass, 2015. http://scholarscompass.vcu.edu/etd/3816.
Full textAbstract:
The famous Four Color Theorem states that any planar graph can be properly colored using at most four colors. However, if we want to properly color the square of a planar graph (or alternatively, color the graph using distinct colors on vertices at distance up to two from each other), we will always require at least \Delta + 1 colors, where \Delta is the maximum degree in the graph. For all \Delta, Wegner constructed planar graphs (even without 3-cycles) that require about \frac{3}{2} \Delta colors for such a coloring.
To prove a stronger upper bound, we consider only planar graphs that contain no 4-cycles and no 5-cycles (but which may contain 3-cycles). Zhu, Lu, Wang, and Chen showed that for a graph G in this class with \Delta \ge 9, we can color G^2 using no more than \Delta + 5 colors. In this thesis we improve this result, showing that for a planar graph G with maximum degree \Delta \ge 32 having no 4-cycles and no 5-cycles, at most \Delta + 3 colors are needed to properly color G^2. Our approach uses the discharging method, and the result extends to list-coloring and other related coloring concepts as well.
40
He, Weihua. "Cycles in graphs and arc colorings in digraphs." Thesis, Paris 11, 2014. http://www.theses.fr/2014PA112352.
Full textAbstract:
Dans cette thèse nous étudions quatre problèmes de théorie des graphes. En particulier,Nous étudions le problème du cycle hamiltonien dans les line graphes, et aussi nous prouvons l’existence de cycles hamiltoniens dans certains sous graphes couvrants d’un line graphe. Notre résultat principal est: Si L(G) est hamiltonien, alors SL(G) est hamiltonien. Grâce à ce résultat nous proposons une conjecture équivalente à des conjectures célèbres. Et nous obtenons deux résultats sur les cycles hamiltoniens disjoints dans les line graphes.Nous considérons alors la bipancyclicité résistante aux pannes des graphes de Cayley engendrés par transposition d’arbres. Nous prouvons que de tels graphes de Cayley excepté le “star graph” ont une bipancyclicité (n − 3)-arête résistante aux pannes.Ensuite nous introduisons la coloration des arcs d’un digraphe sommet distinguant. Nous étudions la relation entre cette notion et la coloration d’arêtes sommet distinguant dans les graphes non orientés. Nous obtenons quelques résultats sur le nombre arc chromatique des graphes orientés (semi-)sommet-distinguant et proposons une conjecture sur ce paramètre. Pour vérifier cette conjecture nous étudions la coloration des arcs d’un digraphe sommet distinguant des graphes orientés réguliers.Finalement nous introduisons la coloration acyclique des arcs d’un graphe orienté. Nous calculons le nombre chromatique acyclique des arcs de quelques familles de graphes orientés et proposons une conjecture sur ce paramètre. Nous considérons les graphes orientés de grande maille et utilisons le Lemme Local de Lovász; d’autre part nous considérons les graphes orientés réguliers aléatoires. Nous prouvons que ces deux classes de graphes vérifient la conjectureIn this thesis, we study four problems in graph theory, the Hamiltonian cycle problem in line graphs, the edge-fault-tolerant bipancyclicity of Cayley graphs generated by transposition trees, the vertex-distinguishing arc colorings in digraph- s and the acyclic arc coloring in digraphs. The first two problems are the classic problem on the cycles in graphs. And the other two arc coloring problems are related to the modern graph theory, in which we use some probabilistic methods. In particular,We first study the Hamiltonian cycle problem in line graphs and find the Hamiltonian cycles in some spanning subgraphs of line graphs SL(G). We prove that: if L(G) is Hamiltonian, then SL(G) is Hamiltonian. Due to this, we propose a conjecture, which is equivalent to some well-known conjectures. And we get two results about the edge-disjoint Hamiltonian cycles in line graphs.Then, we consider the edge-fault-tolerant bipancyclicity of Cayley graphs generated by transposition trees. And we prove that the Cayley graph generated by transposition tree is (n − 3)-edge-fault-tolerant bipancyclic if it is not a star graph.Later, we introduce the vertex-distinguishing arc coloring in digraphs. We study the relationship between the vertex-distinguishing edge coloring in undirected graphs and the vertex-distinguishing arc coloring in digraphs. And we get some results on the (semi-) vertex-distinguishing arc chromatic number for digraphs and also propose a conjecture about it. To verify the conjecture we study the vertex-distinguishing arc coloring for regular digraphs.Finally, we introduce the acyclic arc coloring in digraphs. We calculate the acyclic arc chromatic number for some digraph families and propose a conjecture on the acyclic arc chromatic number. Then we consider the digraphs with high girth by using the Lovász Local Lemma and we also consider the random regular digraphs. And the results of the digraphs with high girth and the random regular digraphs verify the conjecture
41
Luiz, Atílio Gomes 1987. "Sobre a coloração total semiforte." [s.n.], 2014. http://repositorio.unicamp.br/jspui/handle/REPOSIP/275526.
Full textAbstract:
Orientadores: Célia Picinin de Mello, Christiane Neme CamposTexto em português e inglês
Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação
Made available in DSpace on 2018-08-25T12:30:28Z (GMT). No. of bitstreams: 1 Luiz_AtilioGomes_M.pdf: 1439406 bytes, checksum: e2dc07f910b1876087a8f61428919e30 (MD5) Previous issue date: 2014
Resumo: O problema da coloração total semiforte foi introduzido por Zhang et al. por volta de 2005. Este problema consiste em associar cores às arestas e aos vértices de um grafo G=(V(G),E(G)), utilizando o menor número de cores possível, de forma que: (i) quaisquer dois vértices ou duas arestas adjacentes possuam cores distintas; (ii) cada vértice tenha cor diferente das cores das arestas que nele incidem; e, além disso, (iii) para quaisquer dois vértices adjacentes u,v pertencentes a V(G), o conjunto das cores que colorem u e suas arestas incidentes é distinto do conjunto das cores que colorem v e suas arestas incidentes. Denominamos esse menor número de cores para o qual um grafo admite uma coloração total semiforte como número cromático total semiforte. Zhang et al. também determinaram o número cromático total semiforte de algumas famílias clássicas de grafos e observaram que todas elas possuem uma coloração total semiforte com no máximo Delta(G)+3 cores. Com base nesta observação, eles conjeturaram que Delta(G)+3 cores seriam suficientes para construir uma coloração total semiforte para qualquer grafo simples G. Essa conjetura é denominada Conjetura da Coloração Total Semiforte e permanece aberta para grafos arbitrários, tendo sido verificada apenas para algumas famílias de grafos. Nesta dissertação, apresentamos uma resenha dos principais resultados existentes envolvendo a coloração total semiforte. Além disso, determinamos o número cromático total semiforte para as seguintes famílias: os grafos simples com Delta(G)=3 e sem vértices adjacentes de grau máximo; os snarks-flor; os snarks de Goldberg; os snarks de Blanusa generalizados; os snarks de Loupekine LP1; e os grafos equipartidos completos de ordem par. Verificamos que os grafos destas famílias possuem número cromático total semiforte menor ou igual a Delta(G)+2. Investigamos também a coloração total semiforte dos grafos tripartidos e dos grafos equipartidos completos de ordem ímpar e verificamos que os grafos destas famílias possuem número cromático total semiforte menor ou igual a Delta(G)+3. Os resultados obtidos confirmam a validade da Conjetura da Coloração Total Semiforte para todas as famílias consideradas nesta dissertação
Abstract: The adjacent-vertex-distinguishing-total-colouring (AVD-total-colouring) problem was introduced and studied by Zhang et al. around 2005. This problem consists in associating colours to the vertices and edges of a graph G=(V(G),E(G)) using the least number of colours, such that: (i) any two adjacent vertices or adjacent edges receive distinct colours; (ii) each vertex receive a colour different from the colours of its incident edges; and (iii) for any two adjacent vertices u,v of G, the set of colours that color u and its incident edges is distinct from the set of colours that color v and its incident edges. The smallest number of colours for which a graph G admits an AVD-total-colouring is named its AVD-total chromatic number. Zhang et al. determined the AVD-total chromatic number for some classical families of graphs and noted that all of them admit an AVD-total-colouring with no more than Delta(G)+3 colours. Based on this observation, the authors conjectured that Delta(G)+3 colours would be sufficient to construct an AVD-total-colouring for any simple graph G. This conjecture is called the AVD-Total-Colouring Conjecture and remains open for arbitrary graphs, having been verified for a few families of graphs. In this dissertation, we present an overview of the main existing results related to the AVD-total-colouring of graphs. Furthermore, we determine the AVD-total-chromatic number for the following families of graphs: simple graphs with Delta(G)=3 and without adjacent vertices of maximum degree; flower-snarks; Goldberg snarks; generalized Blanusa snarks; Loupekine snarks; and complete equipartite graphs of even order. We verify that the graphs of these families have AVD-total-chromatic number at most Delta(G)+2. Additionally, we verify that the AVD-Total-Colouring Conjecture is true for tripartite graphs and complete equipartite graphs of odd order. These results confirm the validity of the AVD-Total-Colouring Conjecture for all the families considered in this dissertation
Mestrado
Ciência da Computação
Mestre em Ciência da Computação
42
Bobga, Benkam Benedict Johnson Peter D. "Some necessary conditions for list colorability of graphs and a conjecture on completing partial Latin squares." Auburn, Ala, 2008. http://repo.lib.auburn.edu/EtdRoot/2008/FALL/Mathematics_and_Statistics/Dissertation/Bobga_Benkam_22.pdf.
Full text
43
Dross, François. "Vertex partition of sparse graphs." Thesis, Montpellier, 2018. http://www.theses.fr/2018MONTS011/document.
Full textAbstract:
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 de ces ensembles ne contient pas les deux extrémités d'une même arête. Une telle partition est appelée une coloration propre en quatre couleurs. Dans cette thèse, on s'intéresse à l'étude de la structure des graphes peu denses, selon différentes notions de densité. D'une part, on étudie les graphes planaires sans petits cycles, et d'autre part les graphes dont tous les sous-graphes ont un degré moyen peu élevé. Pour ces classes de graphes, on recherche tout d'abord le plus petit nombre de sommets à retirer pour obtenir une forêt, c'est à dire un graphe sans cycles. Cela peut être vu comme une partition des sommets du graphe en un ensemble induisant une forêt et un ensemble de sommets contenant au plus une fraction donnée des sommets du graphe. La motivation première de cette étude est une conjecture d'Albertson et Berman (1976) comme quoi tout graphe planaire admettrait une telle partition où la forêt contient au moins la moitié des sommets du graphe. Dans un second temps, on s'intéresse aux partitions des sommets de ces graphes en deux ensembles, tels que les sous-graphes induits par ces deux ensembles ont des propriétés particulières. Par exemple, ces sous-graphes peuvent être des graphes sans arêtes, des forêts, des graphes de degré borné, ou des graphes dont les composantes connexes ont un nombre borné de sommets. Ces partitions des sommets sont des extensions de la notion de coloration propre de graphe.On montre, pour différentes classes de graphes peu denses, que tous les graphes de ces classes admettent de telles partitions. On s'intéresse également aux aspect algorithmiques de la construction de telles partitionsThe study of vertex partitions of planar graphs was initiated by the Four Colour Theorem, which was conjectured in 1852, and proven in 1976. According to that theorem, one can colour the regions of any planar map by using only four colours, in such a way that any two regions sharing a border have distinct colours. In terms of graph theory, it can be reformulated this way: the vertex set of every planar graph, i.e. every graph that can be represented in the plane such that edges do not cross, can be partitioned into four sets such that no edge has its two endpoints in the same set. Such a partition is called a proper colouring of the graph.In this thesis, we look into the structure of sparse graphs, according to several notions of sparsity. On the one hand, we consider planar graphs with no small cycles, and on the other hand, we consider the graphs where every subgraph has bounded average degree.For these classes of graphs, we first look for the smallest number of vertices that can be removed such that the remaining graph is a forest, that is a graph with no cycles. That can be seen as a partition of the vertices of the graph into a set inducing a forest and a set with a bounded fraction of the vertices of the graph. The main motivation for this study is a the Albertson and Berman Conjecture (1976), which states that every planar graph admits an induced forest containing at least one half of its vertices.We also look into vertex partition of sparse graphs into two sets both inducing a subgraph with some specific prescribed properties. Exemples of such properties can be that they have no edges, or no cycles, that they have bounded degree, or that they have bounded components. These vertex partitions generalise the notion of proper colouring. We show, for different classes of sparse graphs, that every graph in those classes have some specific vertex partition. We also look into algorithmic aspects of these partitions
44
Veeramoni, Mythili Sankaranarayanan. "How To Color A Map." Diss., The University of Arizona, 2014. http://hdl.handle.net/10150/338714.
Full textAbstract:
We study the maximum differential coloring problem, where an n-vertex graph must be colored with colors numbered 1, 2...n such that the minimal difference between the two colors of any edge is maximized. This problem is motivated by coloring maps in which not all countries are contiguous. Since it is known that this problem is NP-hard for general graphs; we consider planar graphs and subclasses thereof. In Chapter 1 we introduce the topic of this thesis and in Chapter 2 we review relevant definitions and basic results. In Chapter 3 we prove that the maximum differential coloring problem remains NP-hard even for planar graphs. Then, we present tight bounds for regular caterpillars and spider graphs and close-to-optimal differential coloring algorithms for general caterpillars and biconnected triangle-free outer-planar graphs. In Chapter 4 we introduce the (d, kn)-differential coloring problem. While it was known that the problem of determining whether a general graph is (2, n)-differential colorable is NP-complete, in this chapter we provide a complete characterization of bipartite, planar and outerplanar graphs that admit (2, n)-differential colorings. We show that it is NP-complete to determine whether a graph admits a (3, 2n)-differential coloring. The same negative result holds for the ([2n/3], 2n)-differential coloring problem, even when input graph is planar. In Chapter 5 we experimentally evaluate and compare several algorithms for coloring a map. Motivated by different application scenarios, we classify our approaches into two categories, depending on the dimensionality of the underlying color space. To cope with the one dimensional color space (e.g., gray-scale colors), we employ the (d, kn)-differential coloring. In Chapter 6 we describe a practical approach for visualizing multiple relationships defined on the same dataset using a geographic map metaphor, where clusters of nodes form countries and neighboring countries correspond to nearby clusters. The aim is to provide a visualization that allows us to compare two or more such maps. In the case where we are considering multiple relationships we also provide an interactive tool to visually explore the effect of combining two or more such relationships. Our method ensures good readability and mental map preservation, based on dynamic node placement with node stability, dynamic clustering with cluster stability, and dynamic coloring with color stability. Finally in Chapter 7 we discuss future work and open problems.
45
Silva, Lenilson dos Reis. "Grafos, coloração, polinômios cromáticos e jogos no processo de ensino aprendizagem da enumeração e da contagem." Universidade de São Paulo, 2018. http://www.teses.usp.br/teses/disponiveis/55/55136/tde-24102018-152915/.
Full textAbstract:
O objetivo deste trabalho é usar jogos e tópicos de Teoria dos Grafos como ferramenta para desenvolver a habilidade da enumeração, que está por trás dos cálculos combinatórios ensinados no Ensino Fundamental e Médio. Mais especificamente, neste trabalho são introduzidos os métodos mais comuns de contagem através de situacões-problema e jogos, como o Nim e o Dominó, que podem ser melhor explorados ao serem descritos atráves dos elementos de um grafo. Com essa motivacão são apresentados conceitos básicos da Teoria dos Grafos e tópicos de coloração de grafos, como o número cromático e os polinômios cromáticos. Esses tópicos fornecem exemplos ricos e motivacionais ao processo de ensino e aprendizagem dos raciocínios combinatórios. Por outro lado, os tópicos abordados contém em si a riqueza e a complexidade da Matemática, como é o caso do Teorema das 4 Cores, demonstrado com o uso da enumeração de todos os casos possíveis. Nesse contexto são apresentados os conceitos de coloração de vértices de grafos dando destaque principal para problemas combinatórios que envolvem o número cromático e o polinômio cromático de um grafo. Complementando o trabalho, são propostas atividades para serem desenvolvidas em sala de aula.The purpose of this work is to use games and topics of Graph Theory as a tool to develop the ability of enumeration, which is behind combinatorial calculations taught in Elementary and High School. More specifically, in this work, the most common methods of counting through problem situations and games, such as Nim and Domino, which can be better explored when described through the elements of a graph. With this motivation are presented basic concepts of the Theory of Graphs and graph coloring topics such as chromatic number and chromatic polynomials. Those topics provide rich and motivational examples to the process of teaching and learning combinatorial reasoning. On the other hand, the topics approach contains in itself the richness and complexity of Mathematics, as is the case with the 4-Color Theorem, demonstrated with the use of the enumeration of all possible cases. In this context are presented concepts of coloring of vertices of graphs giving main highlight to combinatorial problems which involve the chromatic number and the chromatic polynomial of a graph. Complementing the work, activities are proposed to be developed in the classroom.
46
Paris, Gabrielle. "Resolution of some optimisation problems on graphs and combinatorial games." Thesis, Lyon, 2018. http://www.theses.fr/2018LYSE1180/document.
Full textAbstract:
J'ai étudié trois problèmes d'optimisation dans les graphes et les jeux combinatoires.Tout d'abord, les codes identifiants dans les graphes où les sommets font faces à des failles: les codes cherchent à repérer les failles pour les réparer. On s'est intéressé aux codes identifiants dans les graphes circulants en utilisant des plongements de ces graphes dans des grilles infinies.Ensuite, j'ai étudié le jeu de marquage de sommets et le jeu de coloration d'arêtes: ici deux joueurs se font face, le premier cherche à construire une coloration correcte (ou un marquage correct) et le deuxième cherche à l'en empêcher. Pour le jeu de marquage on s'est intéressé aux changements de stratégie gagnante lorsqu'on modifie le graphe. Pour le jeu de coloration d'arêtes on a donné une stratégie gagnante pour le premier joueur pourvu que le graphe considéré admette une certaine décomposition sur les arêtes. On améliore notamment des résultats sur les graphes planaires.Enfin j'ai étudié les jeux à tas purement de casse: deux joueurs à tour de rôle prennent un tas et le cassent en un certain nombre de tas non vides. On s'intéresse aux stratégies gagnantes lorsque les joueurs jouent sur un unique tas contenant n jetons. Ces jeux de pure casse semblent, à l'oeil nu, être réguliers. On a montré que c'est effectivement le cas pour certains et on a donné un test qui permet de déterminer la régularité cas par cas. Un seul cas ne semble pas correspondre à cette régularité: son comportement reste un mystère.En conclusion, je me suis intéressé à trois problèmes bilatéraux qui utilisent différentes méthodes et qui remplissent des propos différents dans le domaine de la combinatoireI studied three optimization problems on graphs and combinatorial games.First, identifying codes were studied : vertices couteract faults. Identifying codes help locate the fault to repare it. We focused on circulant graphs by embedding them on infinite grids.Then, the marking and the coloring games were studied : two player games were one player wants to build something (a proper coloration or a proper marking) and the other wants to prevent the first player from doing so. For the marking game we studied the evolution of the strategy when modifying the graph. For the coloring game we defined a new edge-wise decomposition of graphs and we defined a new strategy on this decomposition that improves known results on planar graphs.In the end, I studied pure breaking games : two players take turns to break a heap of tokens in a given number of non-empty heaps. We focused on winning strategies for the game starting with a unique heap on n tokens. These games seem, on first sight, to be all regular : we showed this is the case for some of them and we gave a test to study one game at a time. Only one of these games does not seem to be regular, its behavior remains a mystery.To sum up, I studied three bilateral problems that use different methods and have different purposes in combinatorics
47
Yahiaoui, Said. "Algorithmes et applications pour la coloration et les alliances dans les graphes." Thesis, Lyon 1, 2013. http://www.theses.fr/2013LYO10274.
Full textAbstract:
Dans cette thèse, nous nous intéressons aux aspects algorithmiques et applications de deux problèmes de graphes, à savoir, la coloration et les alliances. La première partie concerne deux variantes de la coloration de graphes, la coloration Grundy et la coloration forte stricte. Nous commençons par l'étude du nombre Grundy des graphes réguliers. Nous donnons une condition fixe k, nous fournissons une condition nécessaire et suffisante pour que le nombre Grundy d'un graphe régulier soit au moins égal k. Nous caractérisons la classe des graphes cubiques (3-réguliers) pour laquelle le nombre Grundy est égal à 4, et nous présentons un algorithme linéaire pour déterminer le nombre Grundy d'un graphe cubique quelconque. Par ailleurs, en se basant sur la coloration forte stricte pour décomposer les arbres en petites composantes, nous présentons un nouvel algorithme pour l'appariement d'arbres étiquetés, non-ordonnés non-enracinés. Nous montrons que la distance calculée entre deux arbres est une pseudo-métrique. Nos expérimentations sur de larges bases synthétiques et des bases de données réelles confirment nos résultats analytiques et montrent que la distance proposée est précise et son algorithme est scalable. La seconde partie de cette thèse est consacrée aux alliances dans les graphes. Nous proposons un algorithme distribué autostabilisant pour la construction d'alliance offensive globale minimale dans un graphe arbitraire. Nous démontrons que cet algorithme converge sous le démon synchrone en temps linéaire. Ensuite, nous donnons le premier algorithme distribué autostabilisant pour le problème de l'alliance forte globale minimale dans un graphe quelconque. Nous prouvons que cet algorithme est polynomial sous le démon inéquitable distribué. Nous montrons par la suite, comment cet algorithme peut être adapté pour des généralisations du problème, comme la k-alliance forte et l'alliance forte pondérée. Enfin, en se basant sur les propriétés structurelles de l'alliance offensive, nous présentons une solution pour décentraliser le protocole de signalisation SIP. Ceci rend possible son déploiement dans un réseau mobile ad hocThis thesis investigates the algorithmic aspects and applications of two graph problems, namely, colorings and alliances. In the first part, we focus on two variants of the proper vertex coloring, the Grundy coloring and the strict strong coloring. We start by the study of Grundy number for regular graphs. We give a sufficient condition for d-regular graphs with sufficiently large girth to have Grundy number equals d + 1. Then, using graph homomorphism, we obtain a necessary and sufficient condition for d-regular graphs to have Grundy number at least k. Moreover, we characterize cubic graphs (3-regular) for which the Grundy number is d + 1, and present a linear-time algorithm to determine the Grundy number of any arbitrary cubic graph. Subsequently, based on the strict strong coloring, we present an approach for the problem of matching labeled trees. Using this coloring, we propose a new algorithm to deterministically decompose a tree into small components. This leads to an efficient algorithm to measure an accurate distance between unrooted unordered labeled trees. The second part is devoted to the alliances in graphs. We first propose a linear-time self-stabilizing algorithm for the minimal global offensive alliance set problem, under the synchronous distributed scheduler. Then, we give the first self-stabilizing algorithm for the minimal global powerful alliance set problem in arbitrary graphs. Moreover, we show how this algorithm can be adapted to find the minimal global powerful k-alliance and the minimal weighted global powerful alliance sets. We prove that all these algorithms converge in polynomial-time under the unfair distributed scheduler. Finally, based on the structural properties of the offensive alliance, we propose a solution to decentralize the signaling protocol SIP. This enables SIP applications in mobile ad hoc networks
48
Legay, Sylvain. "Quelques problèmes d'algorithmique et combinatoires en théorie des grapphes." Thesis, Université Paris-Saclay (ComUE), 2017. http://www.theses.fr/2017SACLS030/document.
Full textAbstract:
Le sujet de cette thèse est la théorie des graphes. Formellement, un graphe est un ensemble de sommets et un ensemble d’arêtes, c’est à dire de paires de sommets, qui relient les sommets. Cette thèse traite de différents problèmes de décisions binaires ou de minimisations liés à la notion de graphe, et cherche, pour chacun de ces problèmes, à déterminer sa classe de complexité, ou à fournir un algorithme. Le premier chapitre concerne le problème de trouver le plus petit sous-graphe connexe tropical dans un graphe sommet-colorié, c’est à dire le plus petit sous-graphe connexe contenant toutes les couleurs. Le deuxième chapitre concerne les problèmes d’homomorphisme tropical, une généralisation des problèmes de coloriage de graphe. On y trouve un lien entre ces problèmes et plusieurs classes de problèmes d’homomorphismes, dont la classe des Problèmes de Satisfaction de Contraintes. Le troisième chapitre concerne deux variantes lointaines du problème de domination, nommément les problèmes d’alliances globales dans un graphe pondéré et le problème de l’ensemble sûr. Le quatrième chapitre concerne la recherche d’une décomposition arborescente étoilée, c’est à dire une décomposition arborescente dont le rayon des sacs est 1. Enfin, le cinquième chapitre concerne une variante du problème de décider du comportement asymptotique de l’itéré du graphe des bicliquesThis thesis is about graph theory. Formally, a graph is a set of vertices and a set of edges, which are pair of vertices, linking vertices. This thesis deals with various decision problem linked to the notion of graph, and, for each of these problem, try to find its complexity class, or to give an algorithm. The first chapter is about the problem of finding the smallest connected tropical subgraph of a vertex-colored graph, which is the smallest connecter subgraph containing every colors. The second chapter is about problems of tropical homomorphism, a generalization of coloring problem. A link between these problems and several other class of homomorphism problems can be found in this chapter, especially with the class of Constraint Satisfaction Problem. The third chapter is about two variant of the domination problem, namely the global alliance problems in a weighted graph and the safe set problem. The fourth chapter is about the problem of finding a star tree-decomposition, which is a tree-decomposition where the radius of bags is 1. Finally, the fifth chapter is about a variant of the problem of deciding the asymptotic behavior of the iterated biclique graph
49
Morel, Gregory. "Stabilité et coloration des graphes sans P5." Thesis, Grenoble, 2011. http://www.theses.fr/2011GRENM042/document.
Full textAbstract:
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 commençons par dresser un état de l'art complet des méthodes utilisées pour résoudre le problème dans des sous-classes de graphes sans P5, puis nous étudions et résolvons ce problème dans une sous-classe particulière, la classe des graphes sans P5 3-colorables. Nous apportons également des solutions aux problèmes de la reconnaissance et de la coloration de ces graphes, chaque fois en temps linéaire. Enfin, nous définissons, caractérisons et sommes capables de reconnaître les graphes "chain-probe", qui sont les graphes auxquels il est possible de rajouter des arêtes entre certains sommets de sorte qu'ils soient bipartis et sans P5. Les problèmes de ce type proviennent de la génétique et ont également des applications en intelligence artificielleThe class of P5-free graphs, namely the graphs without induced chains with five vertices, is of particular interest in graph theory. Indeed, it is the smallest class defined by only one forbidden connected induced subgraph for which the complexity of the Maximum Independent Set problem is unknown. This problem has many applications in planning, CPU register allocation, molecular biology... In this thesis, we first give a complete state of art of the methods used to solve the problem in P5-free graphs subclasses; then we study and solve this problem in a particular subclass, the class of 3-colorable P5-free graphs. We also bring solutions to recognition and coloring problems of these graphs, each time in linear time. Finally, we define, characterize, and are able to recognize "chain-probe" graphs, namely the graphs for which we can add edges between particular vertices such that the resulting graph is bipartite and P5-free. Problems of this type come from genetics and have application in I.A
50
Sun, Pak Kiu. "Incidence coloring : origins, developments and relation with other colorings." HKBU Institutional Repository, 2007. http://repository.hkbu.edu.hk/etd_ra/826.
Full text