Hadwiger's Conjecture from 1943 states that every graph with no Kt minor is (t-1)-colorable; it remains wide open for t ≥ 7. For positive integers t and s, let Kt-s denote the family of graphs obtained from the complete graph Kt by removing s edges. We say that a graph has no Kt-s minor if it has no H minor for every H in Kt-s. In 1971, Jakobsen proved that every graph with no K7-2 minor is 6-colorable. In this dissertation, we first study the extremal functions for K8-4 minors, K9-6 minors, and K10-12 minors. We show that every graph on n ≥ 9 vertices with at least 4.5n-12 edges has a K8-4 minor, every graph on n ≥ 9 vertices with at least 5n-14 edges has a K9-6 minor, and every graph on n ≥ 10 vertices with at least 5.5n-17.5 edges has a K10-12 minor. We then prove that every graph with no K8-4 minor is 7-colorable, every graph with no K9-6 minor is 8-colorable, and every graph with no K10-12 minor is 9-colorable. The proofs use the extremal functions as well as generalized Kempe chains of contraction-critical graphs obtained by Rolek and Song and a method for finding minors from three different clique subgraphs, originally developed by Robertson, Seymour, and Thomas in 1993 to prove Hadwiger's Conjecture for t = 6. Our main results imply that H-Hadwiger's Conjecture is true for each graph H on 8 vertices that is a subgraph of every graph in K8-4, each graph H on 9 vertices that is a subgraph of every graph in K9-6, and each graph H on 10 vertices that is a subgraph of every graph in K10-12.

No description available.

Submitted by JOSIANE SANTOS DE OLIVEIRA (josianeso) on 2018-11-09T12:26:31Z No. of bitstreams: 1 Juliano da Rosa_.pdf: 355603 bytes, checksum: cebe24b4b8390d0aacde8be31620f889 (MD5) / Made available in DSpace on 2018-11-09T12:26:31Z (GMT). No. of bitstreams: 1 Juliano da Rosa_.pdf: 355603 bytes, checksum: cebe24b4b8390d0aacde8be31620f889 (MD5) Previous issue date: 2018-04-30 / UNISINOS - Universidade do Vale do Rio dos Sinos / Os corantes são substâncias adicionadas aos alimentos e bebidas, com a finalidade de conferir ou intensificar a coloração do produto, tornando-o mais atrativo. Usualmente, são empregados corantes artificiais tanto pelo menor custo de produção, quanto maior estabilidade em relação aos naturais. A busca por padrões de vida mais saudáveis, faz com que as indústrias busquem novas alternativas para atender o mercado. Este trabalho buscará, avaliar a viabilidade de utilização em confeitaria de corantes naturais obtidos por liofilização da variedade de uva black magic, beterraba e mirtilo, em substituição à corantes artificiais. Para tanto, os produtos foram preparados, liofilizados e testados na confeitaria por meio de sua adição ao merengue Francês; teste do °Brix; análise de cor e teste sensorial. Para as amostras em triplicata do °Brix da beterraba, mirtilo e uva, obteve-se respectivamente valores de: 5,92, 8,52 e 15,17°Brix, assim a beterraba possui a menor quantidade de açúcares entre os produtos. Com relação a cor, todos os produtos apresentaram-se satisfatórios, com cor intensificadas proporcionalmente, a medida que, aumenta-se a contração do corante. O teste sensorial, a beterraba dado o seu acentuado gosto característico, torna-se inviável para aplicação na confeitaria. Assim, entre os corantes avaliados: uva black magic, beterraba e mirtilo, apenas os da uva e mirtilo tem características gerais satisfatórias a sua utilização na confeitaria, ressalta-se entretanto, que são necessários estudos complementares quanto a adequação das condições de processamento, armazenamento, determinação de concentrações máximas permitidas, sendo estes os pontos mais críticos da produção. / Dyes are substances added to foods and beverages, in order to confer or intensify the color of the product, making it more attractive. Usually, artificial dyes are used for both the lower cost of production and greater stability over the natural ones. The search for healthier living standards causes industries to seek new alternatives to serve the market. This work will seek to evaluate the viability of confectionery of natural dyes obtained by lyophilization of the variety of black magic grape, beet and blueberry, replacing the artificial dyes. For this, the products were prepared, lyophilized and tested in the confectionery by means of their addition to the French meringue; °Brix test; color analysis and sensory testing. For the triplicate samples of beet, blueberry and grape °Brix, values of 5,92, 8,52 and 15,17 °Brix respectively were obtained, thus the beet has the lowest amount of sugar among the products. With regard to color, all products were satisfactory, with color intensified proportionally, as the dye contraction increases. The sensorial test, the beet given its accentuated characteristic taste, becomes impractical for application in the confectionery. Thus, among the evaluated dyes: black magic grape, beet and blueberry, only those of grape and blueberry have general satisfactory characteristics to their use in the confectionery, it is emphasized however that additional studies are necessary regarding the adequacy of the conditions of processing, storage, determination of maximum permissible concentrations, these being the most critical points of production.

Title: Graph coloring problems Author: Bernard Lidický Department: Department of Applied Mathematics Supervisor: doc. RNDr. Jiří Fiala, Ph.D. Abstract: As the title suggests, the central topic of this thesis is graph coloring. The thesis is divided into three parts where each part focuses on a different kind of coloring. The first part is about 6-critical graphs on surfaces and 6-critical graphs with small crossing number. We give a complete list of all 6-critical graphs on the Klein bottle and complete list of all 6-critical graphs with crossing number at most four. The second part is devoted to list coloring of planar graphs without short cycles. We give a proof that planar graphs without 3-,6-, and 7- cycles are 3-choosable and that planar graphs without triangles and some constraints on 4-cycles are also 3-choosable. In the last part, we focus on a recent concept called packing coloring. It is motivated by a frequency assignment problem where some frequencies must be used more sparsely that others. We improve bounds on the packing chromatic number of the infinite square and hexagonal lattices. Keywords: critical graphs, list coloring, packing coloring, planar graphs, short cycles

A star edge coloring is any edge coloring which is both proper and contains no cycles or path of length four which are bicolored, and the star chromatic index of a graph is the smallest number of colors for which that graph can be star edge colored. Star edge coloring is a relatively new field in graph theory, and very little is known regarding upper bounds of the star chromatic index of most graph types, one of these families being multipartite graphs. We investigate a method for obtaining upper bounds on the star chromatic index of complete multipartite graphs. The basic idea is to decompose such graphs into smaller complete bipartite graphs and applying known upper bounds for such graphs.This method has also been implemented and we present a hypothesis based on simulations.

Nous étudions plusieurs problèmes de coloration dans les graphes, pour certains avec une composante ludique. La coloration à distance 2 d'un graphe est une coloration de ses sommets telle que deux sommets à distance au plus 2 ont des couleurs différentes. Le L(p; q)-étiquetage est une généralisation de ce problème ou les contraintes à distance 1 et 2 sont différentes. Nous donnons des résultats pour ces deux problèmes dans plusieurs classes de graphes peu denses (ayant un faible degré moyen maximum).Le jeu de coloration sur un graphe est un jeu ou deux joueurs, Alice et Bob, colorent tour à tour un des sommets non coloriés d'un graphe, construisant ainsi une coloration propre partielle de plus en plus étendue de ce graphe. Alice tente d'étendre la coloration à l'ensemble du graphe, et Bob tente de l'en empêcher. Nous travaillons sur un invariant de graphe, le degré minmax, dont l'étude permet de déduire des résultats pour le jeu de coloration via l'étude d'un problème structurel, la (1; k)-décomposition d'un graphe, c'est-à-dire la partition de ses arêtes en une forêt et un sous-graphe de degré inférieur ou égal à k.Nous travaillons enfin sur une variante du jeu de coloration nommée jeu de coloration d'incidences, ou Alice et Bob colorient les incidences d'un graphe, pour lequel nous donnons une stratégie efficace pour Alice.Enfin, tout au long de notre mémoire, nous étudions les liens entre la notion de coloration est celle de marquage. Un marquage est un ordre sur les sommets (ou arêtes, ou incidences...) d'un graphe possédant des caractéristiques utiles pour le colorer. Pour nos différents problèmes, nous questionnons l'utilité ou les limites de l'usage de cette notion. / We study several problems of graph coloring, some of them with a game component.A 2-distance coloring of a graph is a vertex coloring where two vertices at distanceat most two have different colors. A L(p; q)-labeling is a generalisation of the distance-2coloring where constraints are different at distance 1 and 2. We give results for thesetwo problems in several classes of sparse graphs (with a low maximal average degree).The coloring game on a graph is a game where two players, Alice and Bob, taketurns coloring an uncolored vertex of the graph, constructing together a proper partialcoloring of the graph extending as time moves on. Alice try to extend the coloringto the whole graph, and Bob try to prevent her to win. We study a graph invariant,the minmax degree, who has consequences on the coloring game through the notion of(1; k)-decomposition of a graph, which is the partition of its edge set into a forest and asubgraph of degree bounded by k.We finally study a variant of the coloring game named incidence coloring game, whereAlice and Bob are coloring the incidences of a graph, and for which we give an efficientstrategy for Alice.Finally, during our thesis, we study the connections between coloring and marking,which is an order on the vertices of a graph (or its edges, or its incidences) havingproperties usefull for its coloring. For our problems, we try to determine the utility andthe limits of a marking-based approach of coloring problems.

Dans cette thèse, nous nous intéressons à différentes notions de colorations sous contraintes. Nous nous intéressons plus spécialement à la coloration acyclique, à la coloration forte d'arêtes et à la coloration d'arêtes sommets adjacents distinguants.Dans le Chapitre 2, nous avons étudié la coloration acyclique. Tout d'abord nous avons cherché à borner le nombre chromatique acyclique pour la classe des graphes de degré maximum borné. Ensuite nous nous sommes attardés sur la coloration acyclique par listes. La notion de coloration acyclique par liste des graphes planaires a été introduite par Borodin, Fon-Der Flaass, Kostochka, Raspaud et Sopena. Ils ont conjecturé que tout graphe planaire est acycliquement 5-liste coloriable. De notre côté, nous avons proposé des conditions suffisantes de 3-liste coloration acyclique des graphes planaires. Dans le Chapitre 3, nous avons étudié la coloration forte d'arêtes des graphes subcubiques en majorant l'indice chromatique fort en fonction du degré moyen maximum. Nous nous sommes également intéressés à la coloration forte d'arêtes des graphes subcubiques sans cycles de longueurs données et nous avons également obtenu une majoration optimale de l'indice chromatique fort pour la famille des graphes planaires extérieurs. Nous avons aussi présenté différents résultats de complexité pour la classe des graphes planaires subcubiques. Enfin, au Chapitre 4, nous avons abordé la coloration d'arêtes sommets adjacents distinguants en déterminant les majorations de l'indice avd-chromatique en fonction du degré moyen maximum. Notre travail s'inscrit dans la continuité de celui effectué par Wang et Wang en 2010. Plus précisément, nous nous sommes focalisés sur la famille des graphes de degré maximum au moins 5. / In this thesis, we are interested in various coloring of graphs under constraints. We study acyclic coloring, strong edge coloring and adjacent vertex-distinguishing edge coloring.In Chapter 2, we consider acyclic coloring and we bound the acyclic chromatic number by a function of the maximum degree of the graph. We also study acyclic list coloring. The notion of acyclic list coloring of planar graphs was introduced by Borodin, Fon-Der Flaass, Kostochka, Raspaud, and Sopena. They conjectured that every planar graph is acyclically 5-choosable. We obtain some sufficient conditions for planar graphs to be acyclically 3-choosable.In Chapter 3, we study strong edge coloring of graphs. We prove some upper bounds of the strong chromatic index of subcubic graphs as a function of the maximum average degree. We also obtain a tight upper bound for the minimum number of colors in a strong edge coloring of outerplanar graphs as a function of the maximum degree. We also prove that the strong edge k-colouring problem, when k=4,5,6, is NP-complete for subcubic planar bipartite graphs with some girth condition. Finally, in Chapter 4, we focus on adjacent vertex-distinguishing edge coloring, or avd-coloring, of graphs. We bound the avd-chromatic number of graphs by a function of the maximum average degree. This work completes a result of Wang and Wang in 2010.

A Probabilistically Checkable Proof (PCP) of a mathematical statement is a proof written in a special manner that allows for efficient probabilistic verification. The celebrated PCP Theorem states that for every family of statements in NP, there is a probabilistic verification procedure that checks the validity of a PCP proof by reading only 3 bits from it. This landmark theorem, and the works leading up to it, laid the foundation for many subsequent works in computational complexity theory, the most prominent among them being the study of inapproximability of combinatorial optimization problems. This thesis focuses on a broad class of combinatorial optimization problems called Constraint Satisfaction Problems (CSPs). In an instance of a CSP problem of arity k, we are given a set of variables taking values from some finite domain, and a set of constraints each involving a subset of at most k variables. The goal is to find an assignment that simultaneously satisfies as many constraints as possible. An alternative formulation of the goal that is commonly used is Gap-CSP, where the goal is to decide whether a CSP instance is satisfiable or far from satisfiable, where the exact meaning of being far from satisfiable varies depending on the problems.We first study Boolean CSPs, where the domain of the variables is {0,1}. The main question we study is the hardness of distinguishing satisfiable Boolean CSP instances from those for which no assignment satisfies more than some epsilon fraction of the constraints. Intuitively, as the arity increases, the CSP gets more complex and thus the hardness parameter epsilon should decrease. We show that for Boolean CSPs of arity k, it is NP-hard to distinguish satisfiable instances from those that are at most 2^{~O(k^{1/3})}/2^k-satisfiable. We also study coloring of graphs and hypergraphs. Given a graph or a hypergraph, a coloring is an assignment of colors to vertices, such that all edges or hyperedges are non-monochromatic. The gap problem is to distinguish instances that are colorable with a small number of colors, from those that require a large number of colors. For graphs, we prove that there exists a constant K_0&gt;0, such that for any K &gt;= K_0, it is NP-hard to distinguish K-colorable graphs from those that require 2^{Omega(K^{1/3})} colors. For hypergraphs, we prove that it is quasi-NP-hard to distinguish 2-colorable 8-uniform hypergraphs of size N from those that require 2^{(log N)^{1/4-o(1)}} colors. In terms of techniques, all these results are based on constructions of PCPs with perfect completeness, that is, PCPs where the probabilistic proof verification procedure always accepts a correct proof. Not only is this a very natural property for proofs, but it can also be an essential requirement in many applications. It has always been particularly challenging to construct PCPs with perfect completeness for NP statements due to limitations in techniques. Our improved hardness results build on and extend many of the current approaches. Our Boolean CSP result and GraphColoring result were proved by adapting the Direct Sum of PCPs idea by Siu On Chan to the perfect completeness setting. Our proof for hypergraph coloring hardness improves and simplifies the recent work by Khot and Saket, in which they proposed the notion of superposition complexity of CSPs. / Ett probabilistiskt verifierbart bevis (eng: Probabilistically Checkable Proof, PCP) av en matematisk sats är ett bevis skrivet på ett speciellt sätt vilket möjliggör en effektiv probabilistisk verifiering. Den berömda PCP-satsen säger att för varje familj av påståenden i NP finns det en probabilistisk verifierare som kontrollerar om en PCP bevis är giltigt genom att läsa endast 3 bitar från det. Denna banbrytande sats, och arbetena som ledde fram till det, lade grunden för många senare arbeten inom komplexitetsteorin, framförallt inom studiet av approximerbarhet av kombinatoriska optimeringsproblem. I denna avhandling fokuserar vi på en bred klass av optimeringsproblem i form av villkorsuppfyllningsproblem (engelska ``Constraint Satisfaction Problems'' CSPs). En instans av ett CSP av aritet k ges av en mängd variabler som tar värden från någon ändlig domän, och ett antal villkor som vart och ett beror på en delmängd av högst k variabler. Målet är att hitta ett tilldelning av variablerna som samtidigt uppfyller så många som möjligt av villkoren. En alternativ formulering av målet som ofta används är Gap-CSP, där målet är att avgöra om en CSP-instans är satisfierbar eller långt ifrån satisfierbar, där den exakta innebörden av att vara ``långt ifrån satisfierbar'' varierar beroende på problemet.Först studerar vi booleska CSPer, där domänen är {0,1}. Den fråga vi studerar är svårigheten av att särskilja satisfierbara boolesk CSP-instanser från instanser där den bästa tilldelningen satisfierar högst en andel epsilon av villkoren. Intuitivt, när ariten ökar blir CSP mer komplexa och därmed bör svårighetsparametern epsilon avta med ökande aritet. Detta visar sig vara sant och ett första resultat är att för booleska CSP av aritet k är det NP-svårt att särskilja satisfierbara instanser från dem som är högst 2^{~O(k^{1/3})}/2^k-satisfierbara. Vidare studerar vi färgläggning av grafer och hypergrafer. Givet en graf eller en hypergraf, är en färgläggning en tilldelning av färger till noderna, så att ingen kant eller hyperkant är monokromatisk. Problemet vi analyserar är att särskilja instanser som är färgbara med ett litet antal färger från dem som behöver många färger. För grafer visar vi att det finns en konstant K_0&gt;0, så att för alla K &gt;= K_0 är det NP-svårt att särskilja grafer som är K-färgbara från dem som kräver minst 2^{Omega(K^{1/3})} färger. För hypergrafer visar vi att det är kvasi-NP-svårt att särskilja 2-färgbara 8-likformiga hypergrafer som har N noder från dem som kräv minst 2^{(log N)^{1/4-o(1)}} färger. Samtliga dessa resultat bygger på konstruktioner av PCPer med perfekt fullständighet. Det vill säga PCPer där verifieraren alltid accepterar ett korrekt bevis. Inte bara är detta en mycket naturlig egenskap för PCPer, men det kan också vara ett nödvändigt krav för vissa tillämpningar. Konstruktionen av PCPer med perfekt fullständighet för NP-påståenden ger tekniska komplikationer och kräver delvis utvecklande av nya metoder. Vårt booleska CSPer resultat och vårt Färgläggning resultat bevisas genom att anpassa ``Direktsumman-metoden'' introducerad av Siu On Chan till fallet med perfekt fullständighet. Vårt bevis för hypergraffärgningssvårighet förbättrar och förenklar ett färskt resultat av Khot och Saket, där de föreslog begreppet superpositionskomplexitet av CSP. / <p>QC 20150916</p>

Le problème de somme coloration minimum (MSCP) et le problème de coloration de bande passante (BCP) sont deux généralisations importantes du problème de coloration des sommets classique avec de nombreuses applications dans divers domaines, y compris la conception de circuits imprimés, la planication, l’allocation de ressource, l’affectation de fréquence dans les réseaux mobiles, etc. Les problèmes MSCP et BCP étant NP-difficiles, les heuristiques et métaheuristiques sont souvent utilisées en pratique pour obtenir des solutions de bonne qualité en un temps de calcul acceptable. Cette thèse est consacrée à des métaheuristiques hybrides pour la résolution efcace des problèmes MSCP et BCP. Pour le problème MSCP, nous présentons deux algorithmes mémétiques qui combinent l’évolution d’une population d’individus avec de la recherche locale. Pour le problème BCP, nous proposons un algorithme hybride à base d’apprentissage faisant coopérer une méthode de construction “informée” avec une procédure de recherche locale. Les algorithmes développés sont évalués sur des instances biens connues et se révèlent très compétitifs par rapport à l’état de l’art. Les principaux composants des algorithmes que nous proposons sont également analysés. / The minimum sum coloring problem (MSCP) and the bandwidth coloring problem (BCP) are two important generalizations of the classical vertex coloring problem with numerous applications in diverse domains, including VLSI design, scheduling, resource allocation and frequency assignment in mobile networks, etc. Since the MSCP and BCP are NP-hard problems, heuristics and metaheuristics are practical solution methods to obtain high quality solutions in an acceptable computing time. This thesis is dedicated to developing effective hybrid metaheuristic algorithms for the MSCP and BCP. For the MSCP, we present two memetic algorithms which combine population-based evolutionary search and local search. An effective algorithm for maximum independent set is devised for generating initial solutions. For the BCP, we propose a learning-based hybrid search algorithm which follows a cooperative framework between an informed construction procedure and a local search heuristic. The proposed algorithms are evaluated on well-known benchmark instances and show highly competitive performances compared to the current state-of-the-art algorithms from the literature. Furthermore, the key issues of these algorithms are investigated and analyzed.

Abstract: This thesis studies five kinds of graph colorings: the circular coloring, the total coloring, the (d; 1)-total labeling, the circular (r; 1)-total labeling, and the acyclic list coloring. We give upper bounds on the circular chromatic number of graphs with small maximum average degree, mad for short. It is proved that if mad(G)<22=9 then G has a 11=4-circular coloring, if mad(G) < 5=2 then G has a 14=5-circular coloring. A conjecture by Behzad and Vizing implies that £G+2 colors are always sufficient for a total coloring of graphs with maximum degree £G. The only open case for planar graphs is for £G = 6. Let G be a planar in which no vertex is contained in cycles of all lengths between 3 and 8. If £G(G) = 6, then G is total 8-colorable. If £G(G) = 8, then G is total 9-colorable. Havet and Yu [23] conjectured that every subcubic graph G ̸=K4 has (2; 1)-total number at most 5. We confirm the conjecture for graphs with maximum average degree less than 7=3 and for flower snarks. We introduce the circular (r; 1)-total labeling. As a relaxation of the aforementioned conjecture, we conjecture that every subcubic graph has circular (2; 1)-total number at most 7. We confirm the conjecture for graphs with maximum average degree less than 5=2. We prove that every planar graph with no cycles of lengths 4, 7 and 8 is acyclically 4-choosable. Combined with recent results, this implies that every planar graph with no cycles of length 4;k; l with 5 6 k < l 6 8 is acyclically 4-choosable.