To see the other types of publications on this topic, follow the link: Graph colouring.
Dissertations / Theses on the topic 'Graph colouring'
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 'Graph colouring.'
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
Rackham, Tom. "Problems in graph colouring." Thesis, University of Oxford, 2009. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.526104.
Full text
2
Williams, Jini. "Aspects of graph colouring." Thesis, Open University, 2004. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.410449.
Full text
3
Ferguson, David G. "Topics in graph colouring and graph structures." Thesis, London School of Economics and Political Science (University of London), 2013. http://etheses.lse.ac.uk/735/.
Full textAbstract:
This thesis investigates problems in a number of different areas of graph theory. These problems are related in the sense that they mostly concern the colouring or structure of the underlying graph. The first problem we consider is in Ramsey Theory, a branch of graph theory stemming from the eponymous theorem which, in its simplest form, states that any sufficiently large graph will contain a clique or anti-clique of a specified size. The problem of finding the minimum size of underlying graph which will guarantee such a clique or anti-clique is an interesting problem in its own right, which has received much interest over the last eighty years but which is notoriously intractable. We consider a generalisation of this problem. Rather than edges being present or not present in the underlying graph, each is assigned one of three possible colours and, rather than considering cliques, we consider cycles. Combining regularity and stability methods, we prove an exact result for a triple of long cycles. We then move on to consider removal lemmas. The classic Removal Lemma states that, for n sufficiently large, any graph on n vertices containing o(n^3) triangles can be made triangle-free by the removal of o(n^2) edges. Utilising a coloured hypergraph generalisation of this result, we prove removal lemmas for two classes of multinomials. Next, we consider a problem in fractional colouring. Since finding the chromatic number of a given graph can be viewed as an integer programming problem, it is natural to consider the solution to the corresponding linear programming problem. The solution to this LP-relaxation is called the fractional chromatic number. By a probabilistic method, we improve on the best previously known bound for the fractional chromatic number of a triangle-free graph with maximum degree at most three. Finally, we prove a weak version of Vizing's Theorem for hypergraphs. We prove that, if H is an intersecting 3-uniform hypergraph with maximum degree D and maximum multiplicity m, then H has at most 2D+m edges. Furthermore, we prove that the unique structure achieving this maximum is m copies of the Fano Plane.
4
Watts, Ivor Llewellyn. "Overlap and fractional graph colouring." Thesis, Open University, 2009. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.505353.
Full textAbstract:
Although a considerable body of material exists concerning the colouring of graphs, there is much less on overlap colourings. In this thesis, we investigate the colouring of certain families of graphs.
5
Waters, Robert James. "Graph colouring and frequency assignment." Thesis, University of Nottingham, 2005. http://eprints.nottingham.ac.uk/10135/.
Full textAbstract:
In this thesis we study some graph colouring problems which arise from mathematical models of frequency assignment in radiocommunications networks, in particular from models formulated by Hale and by Tesman in the 1980s. The main body of the thesis is divided into four chapters. Chapter 2 is the shortest, and is largely self-contained; it contains some early work on the frequency assignment problem, in which each edge of a graph is assigned a positive integer weight, and an assignment of integer colours to the vertices is sought in which the colours of adjacent vertices differ by at least the weight of the edge joining them. The remaining three chapters focus on problems which combine frequency assignment with list colouring, in which each vertex has a list of integers from which its colour must be chosen. In Chapter 3 we study list colourings where the colours of adjacent vertices must differ by at least a fixed integer s, and in Chapter 4 we add the additional restriction that the lists must be sets of consecutive integers. In both cases we investigate the required size of the lists so that a colouring can always be found. By considering the behaviour of these parameters as s tends to infinity, we formulate continuous analogues of the two problems, considering lists which are real intervals in Chapter 4, and arbitrary closed real sets in Chapter 5. This gives rise to two new graph invariants, the consecutive choosability ratio tau(G) and the choosability ratio sigma(G). We relate these to other known graph invariants, provide general bounds on their values, and determine specific values for various classes of graphs.
6
Song, Jian. "Graph colouring with input restrictions." Thesis, Durham University, 2013. http://etheses.dur.ac.uk/6998/.
Full textAbstract:
In this thesis, we research the computational complexity of the graph colouring problem and its variants including precolouring extension and list colouring for graph classes that can be characterised by forbidding one or more induced subgraphs. We investigate the structural properties of such graph classes and prove a number of new properties. We then consider to what extent these properties can be used for efficiently solving the three types of colouring problems on these graph classes. In some cases we obtain polynomial-time algorithms, whereas other cases turn out to be NP-complete. We determine the computational complexity of k-COLOURING, k-PRECOLOURING EXTENSION and LIST k-COLOURING on $P_k$-free graphs. In particular, we prove that k-COLOURING on $P_8$-free graphs is NP-complete, 4-PRECOLOURING EXTENSION $P_7$-free graphs is NP-complete, and LIST 4-COLOURING on $P_6$-free graphs is NP-complete. In addition, we show the existence of an integer r such that k-COLOURING is NP-complete for $P_r$-free graphs with girth 4. In contrast, we determine for any fixed girth $g\geq 4$ a lower bound $r(g)$ such that every $P_{r(g)}$-free graph with girth at least $g$ is 3-colourable. We also prove that 3-LIST COLOURING is NP-complete for complete graphs minus a matching. We present a polynomial-time algorithm for solving 4-PRECOLOURING EXTENSION on $(P_2+P_3)$-free graphs, a polynomial-time algorithm for solving LIST 3-Colouring on $(P_2+P_4)$-free graphs, and a polynomial-time algorithm for solving LIST 3-COLOURING on $sP_3$-free graphs. We prove that LIST k-COLOURING for $(K_{s,t},P_r)$-free graphs is also polynomial-time solvable. We obtain several new dichotomies by combining the above results with some known results.
7
Feghali, Carl. "Topics in graph colouring and extremal graph theory." Thesis, Durham University, 2016. http://etheses.dur.ac.uk/11790/.
Full textAbstract:
In this thesis we consider three problems related to colourings of graphs and one problem in extremal graph theory. Let $G$ be a connected graph with $n$ vertices and maximum degree $\Delta(G)$. Let $R_k(G)$ denote the graph with vertex set all proper $k$-colourings of $G$ and two $k$-colourings are joined by an edge if they differ on the colour of exactly one vertex. Our first main result states that $R_{\Delta(G)+1}(G)$ has a unique non-trivial component with diameter $O(n^2)$. This result can be viewed as a reconfigurations analogue of Brooks' Theorem and completes the study of reconfigurations of colourings of graphs with bounded maximum degree. A Kempe change is the operation of swapping some colours $a$, $b$ of a component of the subgraph induced by vertices with colour $a$ or $b$. Two colourings are Kempe equivalent if one can be obtained from the other by a sequence of Kempe changes. Our second main result states that all $\Delta(G)$-colourings of a graph $G$ are Kempe equivalent unless $G$ is the complete graph or the triangular prism. This settles a conjecture of Mohar (2007). Motivated by finding an algorithmic version of a structure theorem for bull-free graphs due to Chudnovsky (2012), we consider the computational complexity of deciding if the vertices of a graph can be partitioned into two parts such that one part is triangle-free and the other part is a collection of complete graphs. We show that this problem is NP-complete when restricted to five classes of graphs (including bull-free graphs) while polynomial-time solvable for the class of cographs. Finally we consider a graph-theoretic version formulated by Holroyd, Spencer and Talbot (2007) of the famous Erd\H{o}s-Ko-Rado Theorem in extremal combinatorics and obtain some results for the class of trees.
8
Farrugia, Alastair. "Uniqueness and Complexity in Generalised Colouring." Thesis, University of Waterloo, 2003. http://hdl.handle.net/10012/1018.
Full textAbstract:
The study and recognition of graph families (or graph properties) is an essential part of combinatorics. Graph colouring is another fundamental concept of graph theory that can be looked at, in large part, as the recognition of a family of graphs that are colourable according to certain rules.
In this thesis, we study additive induced-hereditary families, and some generalisations, from a colouring perspective. Our main results are:
· Additive induced-hereditary families are uniquely factorisable into irreducible families.
· If P and Q are additive induced-hereditary graph families, then (P,Q)-COLOURING is NP-hard, with the exception of GRAPH 2-COLOURING. Moreover, with the same exception, (P,Q)-COLOURING is NP-complete iff P- and Q-RECOGNITION are both in NP. This proves a 1997 conjecture of Kratochvíl and Schiermeyer.
We also provide generalisations to somewhat larger families. Other results that we prove include:
· a characterisation of the minimal forbidden subgraphs of a hereditary property in terms of its minimal forbidden induced-subgraphs, and vice versa;
· extensions of Mihók's construction of uniquely colourable graphs, and Scheinerman's characterisations of compositivity, to disjoint compositive properties;
· an induced-hereditary property has at least two factorisations into arbitrary irreducible properties, with an explicitly described set of exceptions;
· if G is a generating set for A ο B, where A and B are indiscompositive, then we can extract generating sets for A and B using a greedy algorithm.
9
Chowdhury, Ameerah. "Colouring Subspaces." Thesis, University of Waterloo, 2005. http://hdl.handle.net/10012/1026.
Full textAbstract:
This thesis was originally motivated by considering vector space analogues of problems in extremal set theory, but our main results concern colouring a graph that is intimately related to these vector space analogues. The vertices of the q-Kneser graph are the k-dimensional subspaces of a vector space of dimension v over Fq, and two k-subspaces are adjacent if they have trivial intersection. The new results in this thesis involve colouring the q-Kneser graph when k=2. There are two cases. When k=2 and v=4, the chromatic number is q2+q. If k=2 and v>4, the chromatic number is (q(v-1)-1)/(q-1). In both cases, we characterise the minimal colourings. We develop some theory for colouring the q-Kneser graph in general.
10
Rocha, Leonardo Sampaio. "Algorithmic aspects of graph colouring heuristics." Nice, 2012. https://tel.archives-ouvertes.fr/tel-00759408.
Full textAbstract:
Une coloration propre d’un graphe est une fonction qui attribue une couleur à chaque sommet du graphe avec la restriction que deux sommets voisins ont des couleurs distinctes. Les colorations permettent de modéliser des problèmes d’ordonnancement, d’allocation de fréquences ou de registres. Le problème de trouver une coloration propre d’un graphe qui minimise le nombre de couleurs est un problème NP-difficile très connu. Dans cette thèse nous étudions le nombre de Grundy et le nombre b-chromatique des graphes, deux paramètres qui permettent d’évaluer quelques heuristiques pour le problème d’e la coloration propre. Nous commençons par dresser un état de l’art des résultats sur ces deux paramètres. Puis nous montrons que déterminer le nombre de Grundy est NP-difficile pour un graphe cordal et polynomial sur le graphe sans P5 bipartis. Ensuite nous montrons que déterminer le nombre b-chromatique est NP-difficile pour un graphe cordal et distance-héréditaire, et nous donnons des algorithmes polynomiaux pour certaines sous-classes de graphes blocs, complémentaires des graphes bipartis et P4-sparses. Nous considérons également la complexité à paramètre fixé de déterminer le nombre de Grundy (resp. Nombre b-chromatique) et en particulier, nous montrons que décider sir le nombre de Grundy (ou le nombre b-chromatique) d’un graphe G est au moins V(G)-k admet un algorithme FPT lorsque k est le paramètre. Enfin, nous considérons la complexité de nombreux problèmes liés à la comparaison du nombre de Grundy et nombre b-chromatique avec divers autres paramètres d’un grapheA proper coloring of a graph is a function that assigns a color to each vertex with the restriction that adjacent vertices are assigned with distinct colors. Proper colorings are a natural model for many problems, like scheduling, frequency assignment and register allocation. The problem of finding a proper coloring of a graph with the minimum number of colors is a well-known NP-hard problem. In this thesis we study the Grundy number and the b-chromatic number of graphs, two parameters that evaluate some heuristics for finding proper colorings. We start by giving the state of the art of the results about these parameters. Then, we show that the problem of determining the Grundy Number of bipartite or chordal graphs is NP-hard, but it is solvable in polynomial time for P5-free bipartite graphs. After, we show that the problem of determining the b-chromatic number or a chordal distance-hereditary graph is NP-hard, and we give polynomial-time algorithms for some subclasses of block graphs, complement of bipartite graphs and p4-sparse graphs. We also consider the fixed-parameter tractability of determining the Grundy number and the b-chromatic number, and in particular we show that deciding if the Grundy number (or the b-chromatic number) of a graph G is at least V(G)-k admits an FPT algorithm when k is the parameter. Finally, we consider the computational complexity of many problems related to comparing the b-chromatic number and the Grundy number with various other related parameter of a graph
11
Coker, Thomas David. "Graph colouring and bootstrap percolation with recovery." Thesis, University of Cambridge, 2012. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.610806.
Full text
12
Achlioptas, Demetrios. "Threshold phenomena in random graph colouring and satisfiability." Thesis, National Library of Canada = Bibliothèque nationale du Canada, 1999. http://www.collectionscanada.ca/obj/s4/f2/dsk1/tape7/PQDD_0002/NQ41090.pdf.
Full text
13
Lienart, Emmanuelle Anne Sophie. "Edge-colouring and I-factors in graphs." Thesis, Goldsmiths College (University of London), 2000. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.325549.
Full text
14
Gellert, Laura Kristin [Verfasser]. "On problems related to graph colouring / Laura Kristin Gellert." Ulm : Universität Ulm, 2017. http://d-nb.info/1147484511/34.
Full text
15
Titiloye, Olawale. "Optimization by quantum annealing for the graph colouring problem." Thesis, Manchester Metropolitan University, 2013. http://e-space.mmu.ac.uk/324247/.
Full textAbstract:
Quantum annealing is the quantum equivalent of the well known classical simulated annealing algorithm for combinatorial optimization problems. Despite the appeal of the approach, quantum annealing algorithms competitive with the state of the art for specific problems hardly exist in the literature. Graph colouring is a difficult problem of practical significance that can be formulated as combinatorial optimization. By introducing a symmetry-breaking problem representation, and finding fast incremental techniques to calculate energy changes, a competitive graph colouring algorithm based on quantum annealing is derived. This algorithm is further enhanced by tuning simplification techniques; replica spacing techniques to increase robustness; and a messaging protocol, which enables quantum annealing to efficiently take advantage of multiprocessor environments. Additionally, observations of some patterns in the tuning for random graphs led to a more effective algorithm able to find new upper bounds for several widely-used benchmark graphs, some of which had resisted improvement in the last two decades.
16
Lignos, Ioannis. "Reconfigurations of combinatorial problems : graph colouring and Hamiltonian cycle." Thesis, Durham University, 2017. http://etheses.dur.ac.uk/12098/.
Full textAbstract:
We explore algorithmic aspects of two known combinatorial problems, Graph Colouring and Hamiltonian Cycle, by examining properties of their solution space. One can model the set of solutions of a combinatorial problem $P$ by the solution graph $R(P)$, where vertices are solutions of $P$ and there is an edge between two vertices, when the two corresponding solutions satisfy an adjacency reconfiguration rule. For example, we can define the reconfiguration rule for graph colouring to be that two solutions are adjacent when they differ in colour in exactly one vertex. The exploration of the properties of the solution graph $R(P)$ can give rise to interesting questions. The connectivity of $R(P)$ is the most prominent question in this research area. This is reasonable, since the main motivation for modelling combinatorial solutions as a graph is to be able to transform one into the other in a stepwise fashion, by following paths between solutions in the graph. Connectivity questions can be made binary, that is expressed as decision problems which accept a 'yes' or 'no' answer. For example, given two specific solutions, is there a path between them? Is the graph of solutions $R(P)$ connected? In this thesis, we first show that the diameter of the solution graph $R_{l}(G)$ of vertex $l$-colourings of k-colourable chordal and chordal bipartite graphs $G$ is $O(n^2)$, where $l > k$ and n is the number of vertices of $G$. Then, we formulate a decision problem on the connectivity of the graph colouring solution graph, where we allow extra colours to be used in order to enforce a path between two colourings with no path between them. We give some results for general instances and we also explore what kind of graphs pose a challenge to determine the complexity of the problem for general instances. Finally, we give a linear algorithm which decides whether there is a path between two solutions of the Hamiltonian Cycle Problem for graphs of maximum degree five, and thus providing insights towards the complexity classification of the decision problem.
17
Meeks, Kitty M. F. T. "Graph colourings and games." Thesis, University of Oxford, 2012. http://ora.ox.ac.uk/objects/uuid:a805a379-f891-4250-9a7d-df109f9f52e2.
Full textAbstract:
Graph colourings and combinatorial games are two very widely studied topics in discrete mathematics. This thesis addresses the computational complexity of a range of problems falling within one or both of these subjects. Much of the thesis is concerned with the computational complexity of problems related to the combinatorial game (Free-)Flood-It, in which players aim to make a coloured graph monochromatic ("flood" the graph) with the minimum possible number of flooding operations; such problems are known to be computationally hard in many cases. We begin by proving some general structural results about the behaviour of the game, including a powerful characterisation of the number of moves required to flood a graph in terms of the number of moves required to flood its spanning trees; these structural results are then applied to prove tractability results about a number of flood-filling problems. We also consider the computational complexity of flood-filling problems when the game is played on a rectangular grid of fixed height (focussing in particular on 3xn and 2xn grids), answering an open question of Clifford, Jalsenius, Montanaro and Sach. The final chapter concerns the parameterised complexity of list problems on graphs of bounded treewidth. We prove structural results determining the list edge chromatic number and list total chromatic number of graphs with bounded treewidth and large maximum degree, which are special cases of the List (Edge) Colouring Conjecture and Total Colouring Conjecture respectively. Using these results, we show that the problem of determining either of these quantities is fixed parameter tractable, parameterised by the treewidth of the input graph. Finally, we analyse a list version of the Hamilton Path problem, and prove it to be W[1]-hard when parameterised by the pathwidth of the input graph. These results answer two open questions of Fellows, Fomin, Lokshtanov, Rosamond, Saurabh, Szeider and Thomassen.
18
Outioua, Djedjiga. "Defect-1 Choosability of Graphs on Surfaces." Thesis, Université d'Ottawa / University of Ottawa, 2020. http://hdl.handle.net/10393/40568.
Full textAbstract:
The classical (proper) graph colouring problem asks for a colouring of the vertices of a graph with the minimum number of colours such that no two vertices with the same colour are adjacent. Equivalently the colouring is required to be such that the graph induced by the vertices coloured the same colour has the maximum degree equal to zero. The graph parameter associated with the minimum possible number of colours of a graph is called chromatic number of that graph.
One generalization of this classical problem is to relax the requirement that the maximum degree of the graph induced by the vertices coloured the same colour be zero, and instead allow it to be some integer d. For d = 0, we are back at the classical proper colouring. For other values of d we say that the colouring has defect d.
Another generalization of the classical graph colouring, is list colouring and its associated parameters: choosability and choice number.
The main result of this thesis is to show that every graph G of Euler genus μ is ⌈2 + √(3μ + 3)⌉–choosable with defect 1 (equivalently, with clustering 2). Thus allowing any defect, even 1, reduces the choice number of surface embeddable graphs below the chromatic number of the surface. For example, the chromatic number of the family of toroidal graphs is known to be 7. The bound above implies that toroidal graphs are 5-choosable with defect 1. This strengthens the result of Cowen, Goddard and Jesurum (1997) who showed that toroidal graphs are 5-colourable with defect 1.
In a graph embedded in a surface, two faces that share an edge are called adjacent. We improve the above bound for graphs that have embeddings without adjacent triangles. In particular, we show that every non-planar graph G that can be embedded
in a surface of Euler genus μ without adjacent triangles, is ⌈(5+ √(24μ + 1)) /3⌉–choosable with defect 1. This result generalizes the result of Xu and Zhang (2007) to all the surfaces. They proved that toroidal graphs that have embeddings on the torus without two adjacent triangles are 4-choosable with defect 1.
19
Sulong, Ghazali bin. "Algorithms for timetable construction." Thesis, Cardiff University, 1989. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.253664.
Full text
20
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
21
Kang, Ross J. "Improper colourings of graphs." Thesis, University of Oxford, 2008. http://ora.ox.ac.uk/objects/uuid:a93d8303-0eeb-4d01-9b77-364113b81a63.
Full textAbstract:
We consider a generalisation of proper vertex colouring of graphs, referred to as improper colouring, in which each vertex can only be adjacent to a bounded number t of vertices with the same colour, and we study this type of graph colouring problem in several different settings. The thesis is divided into six chapters. In Chapter 1, we outline previous work in the area of improper colouring. In Chapters 2 and 3, we consider improper colouring of unit disk graphs -- a topic motivated by applications in telecommunications -- and take two approaches, first an algorithmic one and then an average-case analysis. In Chapter 4, we study the asymptotic behaviour of the improper chromatic number for the classical Erdos-Renyi model of random graphs. In Chapter 5, we discuss acyclic improper colourings, a specialisation of improper colouring, for graphs of bounded maximum degree. Finally, in Chapter 6, we consider another type of colouring, frugal colouring, in which no colour appears more than a bounded number of times in any neighbourhood. Throughout the thesis, we will observe a gradient of behaviours: for random unit disk graphs and "large" unit disk graphs, we can greatly reduce the required number of colours relative to proper colouring; in Erdos-Renyi random graphs, we do gain some improvement but only when t is relatively large; for acyclic improper chromatic numbers of bounded degree graphs, we discern an asymptotic difference in only a very narrow range of choices for t.
22
Gravier, Sylvain. "Coloration et produits de graphes." Université Joseph Fourier (Grenoble), 1996. http://www.theses.fr/1996GRE10084.
Full textAbstract:
Dans la première partie, nous étudions la notion de coloration par listes. Un graphe d'ordre n est k-liste colorable si, quelque soit la donnée de n listes de taille k (une par sommet), il est possible d'attribuer, à chaque sommet, une couleur de sa liste, de sorte que deux sommets voisins quelconques aient des couleurs différentes. Nous donnons un rappel des différents résultats classiques sur la coloration par liste. Nous abordons l'aspect de la complexité du problème de liste-coloration. Après une étude des différentes constructions utilisées en théorie des graphes (contraction, identification,…), nous donnons un théorème de type Hajós pour la coloration par listes. Enfin, nous terminons cette étude en abordant la conjecture de Vizing par un angle d'attaque nouveau, ce qui nous permet d'obtenir des résultats sur la classe des graphes sans griffe. Dans un second temps, nous traitons l'aspect algorithmique de la coloration, en donnant un algorithme «séquentiel» d'échange chromatique qui nous permet de colorer et de reconnaître deux nouvelles classes de graphes parfaits. Finalement, nous étudions le comportement de certains invariants de graphes via certains produits. Le nombre d'absorpion du produit croisé d'une chaîne et d'une antichaîne est donné, ainsi que certaines valeurs du produit croisé de deux chaînes. Nous proporons une nouvelle approche de la conjecture de Hedetniemi, en étudiant le problème du nombre chromatique du produit fibré (sous-produit du produit croisé). Nous terminons cette étude sur les prdouits, en abordant deux problèmes classiques de recouvrement, l'hamiltonicité et le plongement d'arbres dans l'hypercube. Nous donnons une conditions nécessaire et suffisante pour que le produit croisé de deux graphes hamiltoniens soit hamiltonien. Nous définissons une large classe d'arbres couvrants l'hypercube, et donnons une partition des arêtes de l'hypercube en de tels arbres
23
Zhang, Peng. "A study on generalized solution concepts in constraint satisfaction and graph colouring." Thesis, University of British Columbia, 2014. http://hdl.handle.net/2429/50022.
Full textAbstract:
The concept of super solutions plays a crucial role in using the constraint satisfaction framework to model many AI problems under uncertain, dynamic, or interactive environments. The availability of large-scale, dynamic, uncertain, and networked data sources in a variety of application domains provides a challenge and opportunity for the constraint programming community, and we expect that super solutions will continue to attract a great deal of interest. In the first part of this thesis, we study the probabilistic behaviour of super solutions of random instances of Boolean Satisability (SAT) and Constraint Satisfaction Problems (CSPs). Our analysis focuses on a special type of super solutions, the (1,0)-super solutions. For random k-SAT, we establish the exact threshold of the phase transition of the solution probability for the cases of k = 2 and 3, and we upper and lower bound the threshold of the phase transition for the case of k ≥ 4. For random CSPs, we derive a non-trivial upper bound on the threshold of phase transitions.
Graph colouring is one of the most well-studied problems in graph theory. A solution to a graph colouring problem is a colouring of the vertices such that each colour class is a stable set. A relatively new generalization of graph colouring is cograph colouring, where each colour class is a cograph. Cographs are the minimum family of graphs containing a single vertex and are closed under complementation and disjoint union. We define the cogchromatic number of a graph G as the minimum number of colours needed by a cograph colouring of G. Several problems related to cograph colouring are studied in the second part of this thesis, including properties of graphs that have cog-chromatic number 2; computational hardness of deciding and approximating the cog-chromatic number of graphs; and graphs that are critical in terms of cog-chromatic numbers. Several interesting constructions of graphs with extremal properties with respect to cograph colouring are also presented.Graduate Studies, College of (Okanagan)
Graduate
24
Heckel, Annika. "Colourings of random graphs." Thesis, University of Oxford, 2016. https://ora.ox.ac.uk/objects/uuid:79e14d55-0589-4e17-bbb5-a216d81b8875.
Full textAbstract:
We study graph parameters arising from different types of colourings of random graphs, defined broadly as an assignment of colours to either the vertices or the edges of a graph. The chromatic number X(G) of a graph is the minimum number of colours required for a vertex colouring where no two adjacent vertices are coloured the same. Determining the chromatic number is one of the classic challenges in random graph theory. In Chapter 3, we give new upper and lower bounds for the chromatic number of the dense random graph G(n,p)) where p ∈ (0,1) is constant. These bounds are the first to match up to an additive term of order o(1) in the denominator, and in particular, they determine the average colour class size in an optimal colouring up to an additive term of order o(1). In Chapter 4, we study a related graph parameter called the equitable chromatic number. This is defined as the minimum number of colours needed for a vertex colouring where no two adjacent vertices are coloured the same and, additionally, all colour classes are as equal in size as possible. We prove one point concentration of the equitable chromatic number of the dense random graph G(n,m) with m = pn(n-1)/2, p < 1-1/e2 constant, on a subsequence of the integers. We also show that whp, the dense random graph G(n,p) allows an almost equitable colouring with a near optimal number of colours. We call an edge colouring of a graph G a rainbow colouring if every pair of vertices is joined by a rainbow path, which is a path where no colour is repeated. The least number of colours where this is possible is called the rainbow connection number rc(G). Since its introduction in 2008 as a new way to quantify how well connected a given graph is, the rainbow connection number has attracted the attention of a great number of researchers. For any graph G, rc(G)≥diam(G), where diam(G) denotes the diameter. In Chapter 5, we will see that in the random graph G(n,p), rainbow connection number 2 is essentially equivalent to diameter 2. More specifically, we consider G ~ G(n,p) close to the diameter 2 threshold and show that whp rc(G) = diam(G) ∈ {2,3}. Furthermore, we show that in the random graph process, whp the hitting times of diameter 2 and of rainbow connection number 2 coincide. In Chapter 6, we investigate sharp thresholds for the property rc(G)≤=r where r is a fixed integer. The results of Chapter 6 imply that for r=2, the properties rc(G)≤=2 and diam(G)≤=2 share the same sharp threshold. For r≥3, the situation seems quite different. We propose an alternative threshold and prove that this is an upper bound for the sharp threshold for rc(G)≤=r where r≥3.
25
Melinder, Victor. "Upper bounds on the star chromatic index for bipartite graphs." Thesis, Linköpings universitet, Matematik och tillämpad matematik, 2020. http://urn.kb.se/resolve?urn=urn:nbn:se:liu:diva-164938.
Full textAbstract:
An area in graph theory is graph colouring, which essentially is a labeling of the vertices or edges according to certain constraints. In this thesis we consider star edge colouring, which is a variant of proper edge colouring where we additionally require the graph to have no two-coloured paths or cycles with length 4. The smallest number of colours needed to colour a graph G with a star edge colouring is called the star chromatic index of G and is denoted
26
Minot, Maël. "Investigating decomposition methods for the maximum common subgraph and sum colouring problems." Thesis, Lyon, 2017. http://www.theses.fr/2017LYSEI120/document.
Full textAbstract:
Notre objectif est d’évaluer et de rendre opérationnelle la décomposition de problèmes d’optimisation sous contraintes. Nous nous sommes intéressés à deux problèmes en particulier : le problème de la recherche d’un plus grand sous-graphe commun (MCIS), et le problème de somme coloration minimale (MSCP). Il s’agit de problèmes NP-difficiles pour lesquels les approches de résolution complètes passent difficilement à l’échelle, et nous proposons de les améliorer à cet égard en décomposant ces problèmes en sous-problèmes indépendants. Les décompositions que nous proposons s’appuient sur la structure du problème initial pour créer des sous-problèmes de tailles équilibrées. Pour le MCIS, nous introduisons une décomposition basée sur la structure du graphe de compatibilité, et nous montrons que cette décomposition permet d’obtenir des sous-problèmes plus équilibrés que la méthode EPS classiquement utilisée pour paralléliser la résolution de problèmes en programmation par contraintes. Pour le MSCP, nous introduisons une nouvelle décomposition arborescente de hauteur bornée, et nous montrons comment tirer partie de la complémentarité de la programmation par contraintes et de la programmation linéaire en nombres entiers pour obtenir et résoudre les sous-problèmes indépendants qui en découlent. Nous proposons également une approche portfolio qui utilise des techniques d’apprentissage automatique pour choisir dynamiquement l’approche la plus performante en fonction du problème à résoudreThe objective of this thesis is, from a general standpoint, to design and evaluate decomposition methods for solving constrained optimisation problems. Two optimisation problems in particular are considered: the maximum common induced subgraph problem, in which the largest common part between two graphs is to be found, and the sum colouring problem, where a graph must be coloured in a way that minimises a sum of weights induced by the employed colours. The maximum common subgraph (MCIS) problem is notably difficult, with a strong applicability in domains such as biology, chemistry and image processing, where the need to measure the similarity between structured objects represented by graphs may arise. The outstanding difficulty of this problem makes it strongly advisable to employ a decomposition method, possibly coupled with a parallelisation of the solution process. However, existing decomposition methods are not well suited to solve the MCIS problem: some lead to a poor balance between subproblems, while others, like tree decomposition, are downright inapplicable. To enable the structural decomposition of such problems, Chmeiss et al. proposed an approach, TR-decomposition, acting at a low level: the microstructure of the problem. This approach had yet to be applied to the MCIS problem. We evaluate it in this context, aiming at reducing the size of the search space while also enabling parallelisation. The second problem that caught our interest is the sum colouring problem. It is an NP-hard variant of the widely known classical graph colouring problem. As in most colouring problems, it basically consists in assigning colours to the vertices of a given graph while making sure no neighbour vertices use the same colour. In the sum colouring problem, however, each colour is associated with a weight. The objective is to minimise the sum of the weights of the colours used by every vertex. This leads to generally harder instances than the classical colouring problem, which simply requires to use as few colours as possible. Only a few exact methods have been proposed for this problem. Among them stand notably a constraint programming (CP) model, a branch and bound approach, as well as an integer linear programming (ILP) model. We led an in-depth investigation of CP's capabilities to solve the sum colouring problem, while also looking into ways to make it more efficient. Additionally, we evaluated a combination of integer linear programming and constraint programming, with the intention of conciliating the strong points of these highly complementary approaches. We took inspiration from the classical backtracking bounded by tree decomposition (BTD) approach. We employ a tree decomposition with a strictly bounded height. We then derive profit from the complementarity of our approaches by developing a portfolio approach, able to choose one of the considered approaches automatically by relying on a number of features extracted from each instance
27
Ouyang, Qiancheng. "Some colouring problems in edge/vertex-coloured graphs : Structural and extremal studies." Electronic Thesis or Diss., université Paris-Saclay, 2023. http://www.theses.fr/2023UPASG060.
Full textAbstract:
La coloration de graphes est l'un des sujets les plus connus, populaires et largement étudiés dans le domaine de la théorie des graphes, avec une vaste littérature comprenant des approches provenant de nombreux domaines ainsi que de nombreux problèmes qui sont encore ouverts et étudiés par divers mathématiciens et informaticiens à travers le monde. Le Problème des Quatre Couleurs, à l'origine de l'étude de la coloration des graphes, a été l'un des problèmes centraux en théorie des graphes au siècle dernier. Il demande s'il est possible de colorer proprement chaque graphe planaire avec quatre couleurs. Malgré son origine théorique, la coloration des graphes a trouvé de nombreuses applications pratiques telles que la planification, les problèmes d'assignation de fréquences, la segmentation, etc. Le Problème des Quatre Couleurs est l'un des problèmes importants parmi de nombreux problèmes de la théorie des graphes chromatiques, à partir duquel de nombreuses variantes et généralisations ont été proposées. Tout d'abord, dans cette thèse, nous visons à optimiser la stratégie de coloration des sommets de graphes et d'hypergraphes avec certaines contraintes données, en combinant le concept de coloration propre et d'élément représentatif de certains sous-ensembles de sommets. D'autre part, en fonction du sujet à colorer, une grande quantité de recherches et de problèmes de graphes à arêtes colorées ont émergé, avec des applications importantes en biologie et en technologies web. Nous fournissons quelques résultats analogues pour certaines questions de connectivité, afin de décrire des graphes dont les arêtes sont attribuées suffisamment de couleurs, garantissant ainsi des arbres couvrants ou des cycles ayant une structure chromatique spécifiqueGraph colouring is one of the best known, popular and extensively researched subject in the field of graph theory, having a wide literature with approaches from many domains and a lot of problems, which are still open and studied by various mathematicians and computer scientists along the world. The Four Colour Problem, originating the study of graph colouring, was one of the central problem in graph theory in the last century, which asks if it is possible to colour every planar graph properly by four colours. Despite the theoretical origin, the graph colouring has found many applications in practice like scheduling, frequency assignment problems, segmentation, etc. The Four Colour Problem is a significant one among many problems in chromatic graph theory, from which many variants and generalizations have been proposed. Firstly, in this thesis, we aim to optimize the strategy to colour the vertex of graphs and hypergraphs with some given constraints, which combines the concept of proper colouring and representative element of some vertex subsets. On the other hand, according to the subject to be coloured, a large amount of research and problems of edge-coloured graphs have emerged, which have important applications to biology and web technologies. We provide some analogous results for some connectivity issues—to describe graphs whose edges are assigned enough colours, that guarantee spanning trees or cycles of a specific chromatic structure
28
Maffray, Frédéric. "Une étude structurelle des graphes parfaits : [thèse soutenue sur un ensemble de travaux]." Grenoble 1, 1992. http://www.theses.fr/1992GRE10158.
Full textAbstract:
Nous introduisons de nouvelles classes de graphes parfaits; établissons les relations d'inclusion entre elles; et, dans plusieurs cas, donnons des algorithmes polynomiaux qui résolvent les problèmes classiques associés à ces classes. Nous considérons tout d'abord le problème de l'existence d'un noyau dans un graphe parfait muni d'une orientation dite normale. Ensuite nous nous intéressons aux graphes de quasi-parité, et montrons que certaines classes de graphes parfaits récemment introduites en font partie. Nous présentons de nouvelles propriétés des chemins à quatre sommets d'un graphe qui entraînent l'ordonnabilité parfaite. Nous introduisons la notion de prédomination entre les sommets d'un graphe, et explorons ses implications dans la théorie des graphes parfaits. En particulier, une nouvelle caractérisation des graphes parfaits en est déduite. Finalement, nous étudions les relations entre certaines fonctions booléennes et les graphes parfaits
29
Sheppard, Nicholas Paul. "Self-Reduction for Combinatorial Optimisation." Thesis, The University of Sydney, 2001. http://hdl.handle.net/2123/797.
Full textAbstract:
This thesis presents and develops a theory of self-reduction. This process is used to map instances of combinatorial optimisation problems onto smaller, more easily solvable instances in such a way that a solution of the former can be readily re-constructed, without loss of information or quality, from a solution of the latter. Self-reduction rules are surveyed for the Graph Colouring Problem, the Maximum Clique Problem, the Steiner Problem in Graphs, the Bin Packing Problem and the Set Covering Problem. This thesis introduces the problem of determining the maximum sequence of self-reductions on a given structure, and shows how the theory of confluence can be adapted from term re-writing to solve this problem by identifying rule sets for which all maximal reduction sequences are equivalent. Such confluence results are given for a number of reduction rules on problems on discrete systems. In contrast, NP-hardness results are also presented for some reduction rules. A probabilistic analysis of self-reductions on graphs is performed, showing that the expected number of self-reductions on a graph tends to zero as the order of the graph tends to infinity. An empirical study is performed comparing the performance of self-reduction, graph decomposition and direct methods of solving the Graph Colouring and Set Covering Problems. The results show that self-reduction is a potentially valuable, but sometimes erratic, method of finding exact solutions to combinatorial problems.
30
Sheppard, Nicholas Paul. "Self-Reduction for Combinatorial Optimisation." University of Sydney. Computer Science, 2001. http://hdl.handle.net/2123/797.
Full textAbstract:
This thesis presents and develops a theory of self-reduction. This process is used to map instances of combinatorial optimisation problems onto smaller, more easily solvable instances in such a way that a solution of the former can be readily re-constructed, without loss of information or quality, from a solution of the latter. Self-reduction rules are surveyed for the Graph Colouring Problem, the Maximum Clique Problem, the Steiner Problem in Graphs, the Bin Packing Problem and the Set Covering Problem. This thesis introduces the problem of determining the maximum sequence of self-reductions on a given structure, and shows how the theory of confluence can be adapted from term re-writing to solve this problem by identifying rule sets for which all maximal reduction sequences are equivalent. Such confluence results are given for a number of reduction rules on problems on discrete systems. In contrast, NP-hardness results are also presented for some reduction rules. A probabilistic analysis of self-reductions on graphs is performed, showing that the expected number of self-reductions on a graph tends to zero as the order of the graph tends to infinity. An empirical study is performed comparing the performance of self-reduction, graph decomposition and direct methods of solving the Graph Colouring and Set Covering Problems. The results show that self-reduction is a potentially valuable, but sometimes erratic, method of finding exact solutions to combinatorial problems.
31
Noel, Jonathan A. "Extremal combinatorics, graph limits and computational complexity." Thesis, University of Oxford, 2016. https://ora.ox.ac.uk/objects/uuid:8743ff27-b5e9-403a-a52a-3d6299792c7b.
Full textAbstract:
This thesis is primarily focused on problems in extremal combinatorics, although we will also consider some questions of analytic and algorithmic nature. The d-dimensional hypercube is the graph with vertex set {0,1}d where two vertices are adjacent if they differ in exactly one coordinate. In Chapter 2 we obtain an upper bound on the 'saturation number' of Qm in Qd. Specifically, we show that for m ≥ 2 fixed and d large there exists a subgraph G of Qd of bounded average degree such that G does not contain a copy of Qm but, for every G' such that G ⊊ G' ⊆ Qd, the graph G' contains a copy of Qm. This result answers a question of Johnson and Pinto and is best possible up to a factor of O(m). In Chapter 3, we show that there exists ε > 0 such that for all k and for n sufficiently large there is a collection of at most 2(1-ε)k subsets of [n] which does not contain a chain of length k+1 under inclusion and is maximal subject to this property. This disproves a conjecture of Gerbner, Keszegh, Lemons, Palmer, Pálvölgyi and Patkós. We also prove that there exists a constant c ∈ (0,1) such that the smallest such collection is of cardinality 2(1+o(1))ck for all k. In Chapter 4, we obtain an exact expression for the 'weak saturation number' of Qm in Qd. That is, we determine the minimum number of edges in a spanning subgraph G of Qd such that the edges of E(Qd)\E(G) can be added to G, one edge at a time, such that each new edge completes a copy of Qm. This answers another question of Johnson and Pinto. We also obtain a more general result for the weak saturation of 'axis aligned' copies of a multidimensional grid in a larger grid. In the r-neighbour bootstrap process, one begins with a set A0 of 'infected' vertices in a graph G and, at each step, a 'healthy' vertex becomes infected if it has at least r infected neighbours. If every vertex of G is eventually infected, then we say that A0 percolates. In Chapter 5, we apply ideas from weak saturation to prove that, for fixed r ≥ 2, every percolating set in Qd has cardinality at least (1+o(1))(d choose r-1)/r. This confirms a conjecture of Balogh and Bollobás and is asymptotically best possible. In addition, we determine the minimum cardinality exactly in the case r=3 (the minimum cardinality in the case r=2 was already known). In Chapter 6, we provide a framework for proving lower bounds on the number of comparable pairs in a subset S of a partially ordered set (poset) of prescribed size. We apply this framework to obtain an explicit bound of this type for the poset 𝒱(q,n) consisting of all subspaces of 𝔽qnordered by inclusion which is best possible when S is not too large. In Chapter 7, we apply the result from Chapter 6 along with the recently developed 'container method,' to obtain an upper bound on the number of antichains in 𝒱(q,n) and a bound on the size of the largest antichain in a p-random subset of 𝒱(q,n) which holds with high probability for p in a certain range. In Chapter 8, we construct a 'finitely forcible graphon' W for which there exists a sequence (εi)∞i=1 tending to zero such that, for all i ≥ 1, every weak εi-regular partition of W has at least exp(εi-2/25log∗εi-2) parts. This result shows that the structure of a finitely forcible graphon can be much more complex than was anticipated in a paper of Lovász and Szegedy. For positive integers p,q with p/q ❘≥ 2, a circular (p,q)-colouring of a graph G is a mapping V(G) → ℤp such that any two adjacent vertices are mapped to elements of ℤp at distance at least q from one another. The reconfiguration problem for circular colourings asks, given two (p,q)-colourings f and g of G, is it possible to transform f into g by recolouring one vertex at a time so that every intermediate mapping is a p,q-colouring? In Chapter 9, we show that this question can be answered in polynomial time for 2 ≤ p/q < 4 and is PSPACE-complete for p/q ≥ 4.
32
Matos, Camacho Stephan. "Introduction to the Minimum Rainbow Subgraph problem." Doctoral thesis, Technische Universitaet Bergakademie Freiberg Universitaetsbibliothek "Georgius Agricola", 2012. http://nbn-resolving.de/urn:nbn:de:bsz:105-qucosa-85490.
Full textAbstract:
Arisen from the Pure Parsimony Haplotyping problem in the bioinformatics, we developed the Minimum Rainbow Subgraph problem (MRS problem): Given a graph $G$, whose edges are coloured with $p$ colours. Find a subgraph $F\\\\subseteq G$ of $G$ of minimum order and with $p$ edges such that each colour occurs exactly once. We proved that this problem is NP-hard, and even APX-hard. Furthermore, we stated upper and lower bounds on the order of such minimum rainbow subgraphs. Several polynomial-time approximation algorithms concerning their approximation ratio and complexity were discussed. Therefore, we used Greedy approaches, or introduced the local colour density $\\\\lcd(T,S)$, giving a ratio on the number of colours and the number of vertices between two subgraphs $S,T\\\\subseteq G$ of $G$. Also, we took a closer look at graphs corresponding to the original haplotyping problem and discussed their special structure.
33
Cereceda, Luis. "Mixing graph colourings." Thesis, London School of Economics and Political Science (University of London), 2007. http://etheses.lse.ac.uk/131/.
Full textAbstract:
This thesis investigates some problems related to graph colouring, or. more precisely. graph re-colouring. Informally, the basic question addressed can be phrased as follows. Suppose one is given a graph G whose vertices can be properly k-coloured. for some k > 2. Is it possible to transform any k-colouring of G into any other by recolouring vertices of G one at a time, making sure a proper k-colouring of G is always maintained? If the answer is in the affirmative, G is said to be k-mixing. The related problem of deciding whether, given two k-colourings of G7 it is possible to transform one into the other by recolouring vertices one at a time, always maintaining a proper k-colouring of G, is also considered. These questions can be considered as having a hearing on certain mathematical and "real-world" problems. In particular, being able to recolour any colouring of a given graph to any other colouring is a necessary pre-requisite for the method of sampling colourings known as Glauber dynamics. The results presented in this thesis may also find application in the context of frequency reassignment: given that the problem of assigning radio frequencies in a wireless communications network is often modelled as a graph colouring problem. the task of re-assigning frequencies in such a network can be thought of as a graph recolouring problem. Throughout the thesis. the emphasis is 011 the algorithmic aspects and the computational complexity of the questions described above. In other words, how easily. in terms of computational resources used, can they be answered? Strong results are obtained for the k = 3 case of the first question, where a characterisation theorem for 3-mixing graphs is given. For the second question. a dichotomy theorem for the complexity of the problem is proved: the problem is solvable in polynomial time for k < 3 and PSPACE-complete for k > 4. In addition, the possible length of a shortest sequence of recolourings between two colourings is investigated, and an interesting connection between the tractability of the problem and its underlying structure is established. Some variants of the above problems are also explored.
34
Chu, Lei. "Colouring Cayley Graphs." Thesis, University of Waterloo, 2005. http://hdl.handle.net/10012/1125.
Full textAbstract:
We will discuss three ways to bound the chromatic number on a Cayley graph.
1. If the connection set contains information about a smaller graph, then these two graphs are related. Using this information, we will show that Cayley graphs cannot have chromatic number three.
2. We will prove a general statement that all vertex-transitive maximal triangle-free graphs on n vertices with valency greater than n/3 are 3-colourable. Since Cayley graphs are vertex-transitive, the bound of general graphs also applies to Cayley graphs.
3. Since Cayley graphs for abelian groups arise from vector spaces, we can view the connection set as a set of points in a projective geometry. We will give a characterization of all large complete caps, from which we derive that all maximal triangle-free cubelike graphs on 2n vertices and valency greater than 2n/4 are either bipartite or 4-colourable.
35
Pirot, Francois. "Coloration de graphes épars." Thesis, Université de Lorraine, 2019. http://www.theses.fr/2019LORR0153/document.
Full textAbstract:
Cette thèse a pour thème la coloration de diverses classes de graphes épars. Shearer montra en 1983 [She83] que le ratio d'indépendance des graphes sans triangle de degré maximal d est au moins (1-o(1))ln d/d, et 13 ans plus tard Johansson [Joh96] démontra que le nombre chromatique de ces graphes est au plus O(d/ln d) quand d tend vers l'infini. Ce dernier résultat fut récemment amélioré par Molloy [Mol19], qui montra que la borne (1+o(1))d/ln d est valide quand d tend vers l'infini.Tandis que le résultat de Molloy s'exprime à l'aide d'un paramètre global, le degré maximal du graphe, nous montrons qu'il est possible de l'étendre à la coloration locale. Il s'agit de la coloration par liste, où la taille de la liste associée à chaque sommet ne dépend que de son degré. Avec une méthode différente se basant sur les propriétés de la distribution hard-core sur les ensembles indépendants d'un graphe, nous obtenons un résultat similaire pour la coloration fractionnaire locale, avec des hypothèses plus faibles. Nous démontrons également un résultat concernant la coloration fractionnaire locale des graphes où chaque sommet est contenu dans un nombre borné de triangles, et une borne principalement optimale sur le taux d'occupation — la taille moyenne des ensembles indépendants — de ces graphes. Nous considérons également les graphes de maille 7, et prouvons des résultats similaires qui améliorent les bornes précédemment connues quand le degré maximal du graphe est au plus 10^7. Finalement, pour les graphes d-réguliers où d vaut 3, 4, ou 5, de maille g variant entre 6 et 12, nous démontrons de nouvelles bornes inférieures sur le ratio d'indépendance.Le Chapitre 2 est dédié à la coloration à distance t d'un graphe, qui généralise la notion de coloration forte des arêtes. Nous cherchons à étendre le théorème de Johansson à la coloration à distance t, par l'exclusion de certains cycles. Le résultat de Johansson s'obtient par exclusion des triangles, ou des cycles de taille k pour n'importe quelle valeur de k. Nous montrons que l'exclusion des cycles de taille 2k, pour n'importe quel k>t, a un effet similaire sur le nombre chromatique à distance t, et sur l'indice chromatique à distance t+1. En outre, quand t est impair, une conclusion similaire peut se faire pour le nombre chromatique à distance t par l'exclusion des cycles de d'une taille impaire fixée valant au moins 3t. Nous étudions l'optimalité de ces résultats à l'aide de constructions de nature combinatoire, algébrique, et probabiliste.Dans le Chapitre 3, nous nous intéressons à la densité bipartie induite des graphes sans triangle, un paramètre relaxant celui de la coloration fractionnaire. Motivés par une conjecture de Esperet, Kang, et Thomassé [EKT19], qui prétend que la densité bipartie induite de graphes sans triangle de degré moyen d est au moins de l'ordre de ln d, nous démontrons cette conjecture quand d est suffisamment grand en termes du nombre de sommets n, à savoir d est au moins de l'ordre de (n ln n)^(1/2). Ce résultat ne pourrait être amélioré que par une valeur de l'ordre de ln n, ce que nous montrons à l'aide d'une construction reposant sur le processus sans triangle. Nos travaux se ramènent à un problème intéressant, celui de déterminer le nombre chromatique fractionnaire maximal d'un graphe épars à n sommets. Nous prouvons des bornes supérieures non triviales pour les graphes sans triangle, et pour les graphes dont chaque sommet appartient à un nombre borné de triangles.Cette thèse est reliée aux nombres de Ramsey. À ce jour, le meilleur encadrement connu sur R(3,t) nous est donné par le résultat de Shearer, et par une analyse récente du processus sans triangle [BoKe13+,FGM13+], ce qui donne(1-o(1)) t²/(4 ln t) < R(3,t) < (1+o(1)) t²/ln t. (1)Beaucoup de nos résultats ne pourraient être améliorés à moins d'améliorer par la même occasion (1), ce qui constituerait une révolution dans la théorie de Ramsey quantitativeThis thesis focuses on generalisations of the colouring problem in various classes of sparse graphs.Triangle-free graphs of maximum degree d are known to have independence ratio at least (1-o(1))ln d/d by a result of Shearer [She83], and chromatic number at most O(d/ln d) by a result of Johansson [Joh96], as d grows to infinity. This was recently improved by Molloy, who showed that the chromatic number of triangle-free graphs of maximum degree d is at most (1+o(1))d/ln d as d grows to infinity.While Molloy's result is expressed with a global parameter, the maximum degree of the graph, we first show that it is possible to extend it to local colourings. Those are list colourings where the size of the list associated to a given vertex depends only on the degree of that vertex. With a different method relying on the properties of the hard-core distribution on the independent sets of a graph, we obtain a similar result for local fractional colourings, with weaker assumptions. We also provide an analogous result concerning local fractional colourings of graphs where each vertex is contained in a bounded number of triangles, and a sharp bound for the occupancy fraction — the average size of an independent set — of those graphs. In another direction, we also consider graphs of girth 7, and prove related results which improve on the previously known bounds when the maximum degree does not exceed 10^7. Finally, for d-regular graphs with d in the set {3,4,5}, of girth g varying between 6 and 12, we provide new lower bounds on the independence ratio.The second chapter is dedicated to distance colourings of graphs, a generalisation of strong edge-colourings. Extending the theme of the first chapter, we investigate minimal sparsity conditions in order to obtain Johansson-like results for distance colourings. While Johansson's result follows from the exclusion of triangles — or actually of cycles of any fixed length — we show that excluding cycles of length 2k, provided that k>t, has a similar effect for the distance-t chromatic number and the distance-(t+1) chromatic index. When t is odd, the same holds for the distance-t chromatic number by excluding cycles of fixed odd length at least 3t. We investigate the asymptotic sharpness of our results with constructions of combinatorial, algebraic, and probabilistic natures.In the third chapter, we are interested in the bipartite induced density of triangle-free graphs, a parameter which conceptually lies between the independence ratio and the fractional chromatic number. Motivated by a conjecture of Esperet, Kang, and Thomassé [EKT19], which states that the bipartite induced density of a triangle-free graph of average degree d should be at least of the order of ln d, we prove that the conjecture holds for when d is large enough in terms of the number of vertices n, namely d is at least of the order of (n ln n)^(1/2). Our result is shown to be sharp up to term of the order of ln n, with a construction relying on the triangle-free process. Our work on the bipartite induced density raises an interesting related problem, which aims at determining the maximum possible fractional chromatic number of sparse graph where the only known parameter is the number of vertices. We prove non trivial upper bounds for triangle-free graphs, and graphs where each vertex belongs to a bounded number of triangles.All the content of this thesis is a collection of specialisations of the off-diagonal Ramsey theory. To this date, the best-known bounds on the off-diagonal Ramsey number R(3,t) come from the aforementioned result of Shearer for the upper-bound, and a recent analysis of the triangle-free process [BoKe13+,FGM13+] for the lower bound, giving(1-o(1)) t²/(4 ln t) < R(3,t) < (1+o(1)) t²/ln t. (1)Many of our results are best possible barring an improvement of (1), which would be a breakthrough in off-diagonal Ramsey theory
36
Angelsmark, Ola. "Constructing Algorithms for Constraint Satisfaction and Related Problems : Methods and Applications." Doctoral thesis, Linköping : Univ, 2005. http://urn.kb.se/resolve?urn=urn:nbn:se:liu:diva-3836.
Full text
37
Meagher, Conor John. "Fractionally total colouring most graphs." Thesis, McGill University, 2004. http://digitool.Library.McGill.CA:80/R/?func=dbin-jump-full&object_id=18201.
Full textAbstract:
A total colouring is the assignment of a colour to each vertex and edge of a graph such that no adjacent vertices or incident edges receive the same colour and no edge receives the same colour as one of its endpoints. If we formulate the problem of finding the total chromatic number as an integer program, we can consider the fractional relaxation known as fractional total colouring. In this thesis we present an algorithm for computing the fractional total chromatic number of a graph, which runs in polynomial time on average. We also present an algorithm that asymptotically almost surely computes the fractional total chromatic number of $G_{n,p}$ for all values of $p$.Une coloration totale d’un graphe est le coloration des arêtes et des sommets telle que deux sommets adjacents ont des couleurs différentes, deux arêtes incidentes ont des couleurs différentes, et une arête a une couleur différente de celles des ses extrémités. Si nous formulons le problème de trouver le nombre chromatique total comme un programme linéaire entier, nous pouvons considérer la relaxation connue comme la coloration totale fractionnaire. Dans cette thèse nous présentons un algorithme pour calculer le nombre chromatique total d’un graphe en temps polynomial en moyenne. Nous présentons aussi un algorithme qui calcule asymptotiquement presque sûrement le nombre chromatique total de $G_{n,p}$ pour toute valeur de $p$. fr
38
Johnson, Antony. "Graph colourings using structured colour sets." Thesis, Open University, 2001. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.367216.
Full text
39
Hind, Hugh Robert Faulkner. "Restricted edge-colourings." Thesis, University of Cambridge, 1988. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.279728.
Full text
40
Marcus, Karina. "Multiflots, métriques et graphes h-parfaits : les cycles impairs dans l'optimisation combinatoire." Phd thesis, Université Joseph Fourier (Grenoble), 1996. http://tel.archives-ouvertes.fr/tel-00005002.
Full textAbstract:
Ce travail se situe dans le domaine de l'optimisation combinatoire. Nous étudions plus particulièrement des caractérisations d'objets pour lesquels des problèmes, qui dans le cas général sont NP-complets, deviennent polynomiaux. Nous traitons d'abord le problème de la faisabilité d'un multiflot, qui possède des applications trés importantes en recherche opérationnelle. C'est à dire, étant donnée la spécification du problème, avec le réseau, les capacités et les demandes, on veut démontrer l'existence ou la non-existence d'une solution. Une façon d'aborder ce problème est de donner des conditions nécessaires et suffisantes pour l'existence d'un multiflot, comme celle connue par condition de coupe. Nous présentons la condition (CC, K_5, F_7), qui généralise la condition de coupe et "raffine" une autre condition existante, la (CC3). La structure du problème de multiflot nous permet aussi de regarder un problème étroitement associé, celui du "packing" de métriques. Nous traitons le cas des packing entiers et demi-entiers, quand la famille de métriques comprend les métriques CC3 et les métriques K_5 et F_7. Nous caractérisons la classe de graphes, et plus généralement de matroïdes, ou l'on peut trouver des packings entiers et demi-entiers, sous quelques hypothèses additionnelles. Puis nous nous intéressons aux propriétés générales des graphes h- et t-parfaits, et au problème de coloration associé. Les résultats que nous présentons donnent des bornes pour leur nombres chromatiques, et des classes qui satisfont une conjecture de Shepherd. Enfin nous présentons la hiérarchie des graphes étudiés, qui est obtenu grâce à des outils comme les graphes faiblement bipartis, les clutters binaires et les matrices à composantes 0,1. Nous clôturons ce mémoire en précisant quelques directions de recherche qui pourront donner suite à ce travail, aussi bien sur le sujet de la faisabilité des problèmes de multiflot, que sur la coloration des graphes h- et t-parfaits.
41
Ali, Seema. "Colouring generalized Kneser graphs and homotopy theory." Thesis, National Library of Canada = Bibliothèque nationale du Canada, 1998. http://www.collectionscanada.ca/obj/s4/f2/dsk2/tape15/PQDD_0014/MQ34938.pdf.
Full text
42
Müller, Tobias. "Random geometric graphs : colouring and related topics." Thesis, University of Oxford, 2006. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.437019.
Full text
43
Gao, Rong. "Some colouring problems for Pseudo-Random Graphs." Thesis, University of Essex, 2008. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.494355.
Full text
44
Hardy, Bradley. "Heuristic methods for colouring dynamic random graphs." Thesis, Cardiff University, 2018. http://orca.cf.ac.uk/109385/.
Full textAbstract:
Many real-world operational research problems can be reformulated into static graph colouring problems. However, such problems might be better represented as dynamic graphs if their size and/or constraints change over time. In this thesis, we explore heuristics approaches for colouring dynamic random graphs. We consider two di�erent types of dynamic graph: edge dynamic and vertex dynamic. We also consider two di�erent change scenarios for each of these dynamic graph types: without future change information (i. e. random change) and with probabilistic future change information. By considering a dynamic graph as a series of static graphs, we propose a �modi �cation approach� which modi�es a feasible colouring (or solution) for the static representation of a dynamic graph at one time-step into a colouring for the subsequent time-step. In almost all cases, this approach is bene�cial with regards to either improving quality or reducing computational e�ort when compared against using a static graph colouring approach for each time-step independently. In fact, for test instances with small amounts of change between time-steps, this approach can be bene�cial with regards to both quality and computational e�ort When probabilistic future change information is available, we propose a �twostage approach� which �rst attempts to identify a feasible colouring for the current time-step using our �modi�cation approach�, and then attempts to increase the robustness of the colouring with regards to potential future changes. For both the edge and vertex dynamic cases, this approach was shown to decrease the �problematic� change introduced between time-steps. A clear trade-o� can be observed between the quality of a colouring and its potential robustness, such that a colouring with more colours (i. e. reduced quality) can be made more robust.
45
Gerke, Stefanie. "Weighted colouring and channel assignment." Thesis, University of Oxford, 2000. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.325977.
Full text
46
Pirot, Francois. "Coloration de graphes épars." Electronic Thesis or Diss., Université de Lorraine, 2019. http://www.theses.fr/2019LORR0153.
Full textAbstract:
Cette thèse a pour thème la coloration de diverses classes de graphes épars. Shearer montra en 1983 [She83] que le ratio d'indépendance des graphes sans triangle de degré maximal d est au moins (1-o(1))ln d/d, et 13 ans plus tard Johansson [Joh96] démontra que le nombre chromatique de ces graphes est au plus O(d/ln d) quand d tend vers l'infini. Ce dernier résultat fut récemment amélioré par Molloy [Mol19], qui montra que la borne (1+o(1))d/ln d est valide quand d tend vers l'infini.Tandis que le résultat de Molloy s'exprime à l'aide d'un paramètre global, le degré maximal du graphe, nous montrons qu'il est possible de l'étendre à la coloration locale. Il s'agit de la coloration par liste, où la taille de la liste associée à chaque sommet ne dépend que de son degré. Avec une méthode différente se basant sur les propriétés de la distribution hard-core sur les ensembles indépendants d'un graphe, nous obtenons un résultat similaire pour la coloration fractionnaire locale, avec des hypothèses plus faibles. Nous démontrons également un résultat concernant la coloration fractionnaire locale des graphes où chaque sommet est contenu dans un nombre borné de triangles, et une borne principalement optimale sur le taux d'occupation — la taille moyenne des ensembles indépendants — de ces graphes. Nous considérons également les graphes de maille 7, et prouvons des résultats similaires qui améliorent les bornes précédemment connues quand le degré maximal du graphe est au plus 10^7. Finalement, pour les graphes d-réguliers où d vaut 3, 4, ou 5, de maille g variant entre 6 et 12, nous démontrons de nouvelles bornes inférieures sur le ratio d'indépendance.Le Chapitre 2 est dédié à la coloration à distance t d'un graphe, qui généralise la notion de coloration forte des arêtes. Nous cherchons à étendre le théorème de Johansson à la coloration à distance t, par l'exclusion de certains cycles. Le résultat de Johansson s'obtient par exclusion des triangles, ou des cycles de taille k pour n'importe quelle valeur de k. Nous montrons que l'exclusion des cycles de taille 2k, pour n'importe quel k>t, a un effet similaire sur le nombre chromatique à distance t, et sur l'indice chromatique à distance t+1. En outre, quand t est impair, une conclusion similaire peut se faire pour le nombre chromatique à distance t par l'exclusion des cycles de d'une taille impaire fixée valant au moins 3t. Nous étudions l'optimalité de ces résultats à l'aide de constructions de nature combinatoire, algébrique, et probabiliste.Dans le Chapitre 3, nous nous intéressons à la densité bipartie induite des graphes sans triangle, un paramètre relaxant celui de la coloration fractionnaire. Motivés par une conjecture de Esperet, Kang, et Thomassé [EKT19], qui prétend que la densité bipartie induite de graphes sans triangle de degré moyen d est au moins de l'ordre de ln d, nous démontrons cette conjecture quand d est suffisamment grand en termes du nombre de sommets n, à savoir d est au moins de l'ordre de (n ln n)^(1/2). Ce résultat ne pourrait être amélioré que par une valeur de l'ordre de ln n, ce que nous montrons à l'aide d'une construction reposant sur le processus sans triangle. Nos travaux se ramènent à un problème intéressant, celui de déterminer le nombre chromatique fractionnaire maximal d'un graphe épars à n sommets. Nous prouvons des bornes supérieures non triviales pour les graphes sans triangle, et pour les graphes dont chaque sommet appartient à un nombre borné de triangles.Cette thèse est reliée aux nombres de Ramsey. À ce jour, le meilleur encadrement connu sur R(3,t) nous est donné par le résultat de Shearer, et par une analyse récente du processus sans triangle [BoKe13+,FGM13+], ce qui donne(1-o(1)) t²/(4 ln t) < R(3,t) < (1+o(1)) t²/ln t. (1)Beaucoup de nos résultats ne pourraient être améliorés à moins d'améliorer par la même occasion (1), ce qui constituerait une révolution dans la théorie de Ramsey quantitativeThis thesis focuses on generalisations of the colouring problem in various classes of sparse graphs.Triangle-free graphs of maximum degree d are known to have independence ratio at least (1-o(1))ln d/d by a result of Shearer [She83], and chromatic number at most O(d/ln d) by a result of Johansson [Joh96], as d grows to infinity. This was recently improved by Molloy, who showed that the chromatic number of triangle-free graphs of maximum degree d is at most (1+o(1))d/ln d as d grows to infinity.While Molloy's result is expressed with a global parameter, the maximum degree of the graph, we first show that it is possible to extend it to local colourings. Those are list colourings where the size of the list associated to a given vertex depends only on the degree of that vertex. With a different method relying on the properties of the hard-core distribution on the independent sets of a graph, we obtain a similar result for local fractional colourings, with weaker assumptions. We also provide an analogous result concerning local fractional colourings of graphs where each vertex is contained in a bounded number of triangles, and a sharp bound for the occupancy fraction — the average size of an independent set — of those graphs. In another direction, we also consider graphs of girth 7, and prove related results which improve on the previously known bounds when the maximum degree does not exceed 10^7. Finally, for d-regular graphs with d in the set {3,4,5}, of girth g varying between 6 and 12, we provide new lower bounds on the independence ratio.The second chapter is dedicated to distance colourings of graphs, a generalisation of strong edge-colourings. Extending the theme of the first chapter, we investigate minimal sparsity conditions in order to obtain Johansson-like results for distance colourings. While Johansson's result follows from the exclusion of triangles — or actually of cycles of any fixed length — we show that excluding cycles of length 2k, provided that k>t, has a similar effect for the distance-t chromatic number and the distance-(t+1) chromatic index. When t is odd, the same holds for the distance-t chromatic number by excluding cycles of fixed odd length at least 3t. We investigate the asymptotic sharpness of our results with constructions of combinatorial, algebraic, and probabilistic natures.In the third chapter, we are interested in the bipartite induced density of triangle-free graphs, a parameter which conceptually lies between the independence ratio and the fractional chromatic number. Motivated by a conjecture of Esperet, Kang, and Thomassé [EKT19], which states that the bipartite induced density of a triangle-free graph of average degree d should be at least of the order of ln d, we prove that the conjecture holds for when d is large enough in terms of the number of vertices n, namely d is at least of the order of (n ln n)^(1/2). Our result is shown to be sharp up to term of the order of ln n, with a construction relying on the triangle-free process. Our work on the bipartite induced density raises an interesting related problem, which aims at determining the maximum possible fractional chromatic number of sparse graph where the only known parameter is the number of vertices. We prove non trivial upper bounds for triangle-free graphs, and graphs where each vertex belongs to a bounded number of triangles.All the content of this thesis is a collection of specialisations of the off-diagonal Ramsey theory. To this date, the best-known bounds on the off-diagonal Ramsey number R(3,t) come from the aforementioned result of Shearer for the upper-bound, and a recent analysis of the triangle-free process [BoKe13+,FGM13+] for the lower bound, giving(1-o(1)) t²/(4 ln t) < R(3,t) < (1+o(1)) t²/ln t. (1)Many of our results are best possible barring an improvement of (1), which would be a breakthrough in off-diagonal Ramsey theory
47
Sanchez-Arroyo, Abdon. "Colourings, complexity, and some related topics." Thesis, University of Oxford, 1991. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.280009.
Full text
48
Hetherington, Timothy J. "List-colourings of near-outerplanar graphs." Thesis, Nottingham Trent University, 2007. http://irep.ntu.ac.uk:80/R/?func=dbin-jump-full&object_id=195759.
Full textAbstract:
A list-colouring of a graph is an assignment of a colour to each vertex v from its own list L(v) of colours. Instead of colouring vertices we may want to colour other elements of a graph such as edges, faces, or any combination of vertices, edges and faces. In this thesis we will study several of these different types of list-colouring, each for the class of a near-outerplanar graphs. Since a graph is outerplanar if it is both K4-minor-free and K2,3-minor-free, then by a near-outerplanar graph we mean a graph that is either K4-minor-free or K2,3-minor-free. Chapter 1 gives an introduction to the area of graph colourings, and includes a review of several results and conjectures in this area. In particular, four important and interesting conjectures in graph theory are the List-Edge-Colouring Conjecture (LECC), the List-Total-Colouring Conjecture (LTCC), the Entire Colouring Conjecture (ECC), and the List-Square-Colouring Conjecture (LSCC), each of which will be discussed in Chapter 1. In Chapter 2 we include a proof of the LECC and LTCC for all near-outerplanar graphs. In Chapter 3 we will study the list-colouring of a near-outerplanar graph in which vertices and faces, edges and faces, or vertices, edges and face are to be coloured. The results for the case when all elements are to be coloured will prove the ECC for all near-outerplanar graphs. In Chapter 4 we will study the list-colouring of the square of a K4-minor-free graph, and in Chapter 5 we will study the list-colouring of the square of a K2,3-minor-free graph. In Chapter 5 we include a proof of the LSCC for all K2,3-minor-free graphs with maximum degree at least six.
49
Allen, S. M. "Extending the edge-colourings of graphs." Thesis, University of Reading, 1996. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.320107.
Full text
50
Rombach, Michaela Puck. "Colouring, centrality and core-periphery structure in graphs." Thesis, University of Oxford, 2013. http://ora.ox.ac.uk/objects/uuid:7326ecc6-a447-474f-a03b-6ec244831ad4.
Full textAbstract:
Krivelevich and Patkós conjectured in 2009 that χ(G(n, p)) ∼ χ=(G(n, p)) ∼ χ∗=(G(n, p)) for C/n < p < 1 − ε, where ε > 0. We prove this conjecture for n−1+ε1 < p < 1 − ε2 where ε1, ε2 > 0. We investigate several measures that have been proposed to indicate centrality of nodes in networks, and find examples of networks where they fail to distinguish any of the vertices nodes from one another. We develop a new method to investigate core-periphery structure, which entails identifying densely-connected core nodes and sparsely-connected periphery nodes. Finally, we present an experiment and an analysis of empirical networks, functional human brain networks. We found that reconfiguration patterns of dynamic communities can be used to classify nodes into a stiff core, a flexible periphery, and a bulk. The separation between this stiff core and flexible periphery changes as a person learns a simple motor skill and, importantly, it is a good predictor of how successful the person is at learning the skill. This temporally defined core-periphery organisation corresponds well with the core- periphery detected by the method that we proposed earlier the static networks created by averaging over the subjects dynamic functional brain networks.