abstract: Every graph can be colored with one more color than its maximum degree. A well-known theorem of Brooks gives the precise conditions under which a graph can be colored with maximum degree colors. It is natural to ask for the required conditions on a graph to color with one less color than the maximum degree; in 1977 Borodin and Kostochka conjectured a solution for graphs with maximum degree at least 9: as long as the graph doesn't contain a maximum-degree-sized clique, it can be colored with one fewer than the maximum degree colors. This study attacks the conjecture on multiple fronts. The first technique is an extension of a vertex shuffling procedure of Catlin and is used to prove the conjecture for graphs with edgeless high vertex subgraphs. This general approach also bears more theoretical fruit. The second technique is an extension of a method Kostochka used to reduce the Borodin-Kostochka conjecture to the maximum degree 9 case. Results on the existence of independent transversals are used to find an independent set intersecting every maximum clique in a graph. The third technique uses list coloring results to exclude induced subgraphs in a counterexample to the conjecture. The classification of such excludable graphs that decompose as the join of two graphs is the backbone of many of the results presented here. The fourth technique uses the structure theorem for quasi-line graphs of Chudnovsky and Seymour in concert with the third technique to prove the Borodin-Kostochka conjecture for claw-free graphs. The fifth technique adds edges to proper induced subgraphs of a minimum counterexample to gain control over the colorings produced by minimality. The sixth technique adapts a recoloring technique originally developed for strong coloring by Haxell and by Aharoni, Berger and Ziv to general coloring. Using this recoloring technique, the Borodin-Kostochka conjectured is proved for graphs where every vertex is in a large clique. The final technique is naive probabilistic coloring as employed by Reed in the proof of the Borodin-Kostochka conjecture for large maximum degree. The technique is adapted to prove the Borodin-Kostochka conjecture for list coloring for large maximum degree. / Dissertation/Thesis / Ph.D. Mathematics 2013

Nos recherches traitent de coloration de graphes avec des contraintes de distance (coloration de packing) ou des contraintes sur le voisinage (coloration de Grundy). Soit S={si| i in N*} une série croissante d’entiers. Une S -coloration de packing est une coloration propre de sommets telle que tout ensemble coloré i est un si-packing (un ensemble où tous les sommets sont à distance mutuelle supérieure à si). Un graphe G est (s1,... ,sk)-colorable si il existe une S -coloration de packing de G avec les couleurs 1, ...,,k. Une coloration de Grundy est une coloration propre de sommets telle que pour tout sommet u coloré i, u est adjacent à un sommet coloré j, pour chaque j<i.Dans cette exposé, nous présentons des résultats connus à propos de la S-coloration de packing. Nous apportons de nouveaux résultats à propos de la S-coloration de packing, pour des classes de graphes telles que les chemins, les cycles et les arbres. Nous étudions en détail la complexité du problème de complexité associé à la S-coloration de packing, noté S -COL. Pour certaines instances de S -COL, nous caractérisons des dichotomies entre problèmes NP-complets et problèmes résolubles en tempspolynomial. Nous nous intéressons aux différentes grilles infinies, les grilles hexagonale, carrée, triangulaire et du roi et nous déterminons des propriétés de subdivisions d’un i-packing en plusieurs j-packings, avec j>i. Ces résultats nous permettent de déterminer des S-colorations de packings de ces grilles pour plusieurs séries d’entiers. Nous examinons une classe de graphe jamais étudiée en ce qui concerne la S -coloration de packing: les graphes subcubiques. Nous déterminons que tous les graphes subcubiques sont (1,2,2,2,2,2,2)-colorables et (1,1,2,2,3)-colorables. Un certain nombre de résultats sont prouvés pour certaines sous-classes des graphes subcubiques. Pour finir, nous nous intéressons au nombre de Grundy des graphes réguliers. Nous déterminons une caractérisation des graphes cubiques avec un nombre de Grundy de 4. De plus, nous prouvons que tous les graphes r-réguliers sans carré induit ont pour nombre de Grundy de r+1, pour r<5. / Our research are about graph coloring with distance constraints (packing coloring) or neighborhood constraints (Grundy coloring). Let S={si| i in N*} be a non decreasing sequence of integers. An S-packing coloring is a proper coloring such that every set of color i is an si-packing (a set of vertices at pairwise distance greater than si). A graph G is (s1,... ,sk)-colorable if there exists a packing coloring of G with colors 1,... ,k. A Grundy coloring is a proper vertex coloring such that for every vertex of color i, u is adjacent to a vertex of color j, for each j<i.In this presentation, we present results about S-packing coloring. We prove new results about the S-coloring of graphs including paths, cycles and trees. We study the complexity problem associated to the S-packing coloring, this problem is denoted S-COL. For some instances of S-COL, we characterize dichotomy between NP-complete problems and problems solved by a polynomial time algorithm. We study also different lattices, the hexagonal, square, triangular and king lattices. We determine properties on the subdivision of an i-packing in several j-packings, for j>i. These results allow us to determine S-packing coloring of these lattices for several sequences of integers. We examine a class of graph that has never been studied for S-packing coloring: the subcubic graphs. We determine that every subcubic graph is (1,2,2,2,2,2,2)-colorable and (1,1,2,2,3)-colorable. Few results are proven about some subclasses. Finally, we study the Grundy number of regular graphs. We determine a characterization of the cubic graphs with Grundy number 4. Moreover, we prove that every r-regular graph without induced square has Grundy number r+1, for r<5.

Orientador: Célia Picinin de Mello / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-27T04:52:30Z (GMT). No. of bitstreams: 1 Vilas-Boas_AloisiodeMenezes_M.pdf: 3075345 bytes, checksum: 59f85d259c9a55bce9d3409c06dd71fa (MD5) Previous issue date: 2015 / Resumo: Seja G um grafo simples. Uma coloração de arestas semiforte de G é uma coloração de arestas de G onde para cada par de vértices adjacentes u,v de G, o conjunto das cores atribuídas às arestas de u é diferente do conjunto das cores atribuídas às arestas de v. O índice cromático semiforte de G, denotado por chi'a(G), é o menor número de cores necessário para construir uma coloração de arestas semiforte para G. Esta coloração foi proposta por Zhang et al. em 2002. Nesse mesmo artigo, os autores conjecturaram que todo grafo simples conexo G, G diferente de C_5, com pelo menos três vértices possui chi'a(G) menor ou igual a Delta(G)+2. Esta conjectura conhecida como conjectura da coloração de arestas semiforte está aberta para grafos arbitrários, mas é válida para algumas classes de grafos. Nesta dissertação, apresentamos alguns resultados sobre a coloração de arestas semiforte. Em seguida, focamos em grafos split. Provamos a conjectura da coloração de arestas semiforte para algumas famílias destes grafos, dentre elas, os split-completos e os split-indiferença. Além disso, determinamos o índice cromático semiforte dos grafos split-indiferença com vértice universal. Para grafos split-indiferença sem vértice universal, exibimos condições para que seu índice cromático semiforte seja igual a Delta(G)+1 e conjecturamos chi'a(G) = Delta(G)+2 caso contrário / Abstract: Let G be a simple graph. An adjacent strong edge-coloring of G is an edge-coloring of G such that for each pair of adjacent vertices u,v of G, the set of colors assigned to the edges incident with u differs from the set of colors assigned to the edges incident with v. The adjacent strong chromatic index, denoted chi'a(G), of G is the minimum number of colors required to produce an adjacent strong edge-coloring for G. This coloring was proposed by Z. Zhang et al. In the same article, the authors conjectured that every simple connected graph G with at least three vertices and G not equal to C_5 (a 5-cycle) has chi'a(G) less or equal then Delta(G)+2. This conjecture is open for arbitrary graphs, but it holds for some classes of graphs. In this dissertation, we present some results on adjacent strong edge-coloring. Then, we focus on split graphs. We prove the conjecture for some families of split graphs including split-complete graphs and split-indifference graphs. Moreover, we determine a necessary condition for split-complete graphs G to have chi'a(G) = Delta(G)+1 and we determine the adjacent strong chromatic index for split-indifference graphs with a universal vertex. For a split-indifference graph G without universal vertices, we give conditions for its adjacent strong chromatic index to be Delta(G)+1 and we conjecture that chi'a(G) = Delta(G)+2, otherwise / Mestrado / Ciência da Computação / Mestre em Ciência da Computação

Le sujet de cette thèse est la théorie des graphes. Formellement, un graphe est un ensemble de sommets et un ensemble d’arêtes, c’est à dire de paires de sommets, qui relient les sommets. Cette thèse traite de différents problèmes de décisions binaires ou de minimisations liés à la notion de graphe, et cherche, pour chacun de ces problèmes, à déterminer sa classe de complexité, ou à fournir un algorithme. Le premier chapitre concerne le problème de trouver le plus petit sous-graphe connexe tropical dans un graphe sommet-colorié, c’est à dire le plus petit sous-graphe connexe contenant toutes les couleurs. Le deuxième chapitre concerne les problèmes d’homomorphisme tropical, une généralisation des problèmes de coloriage de graphe. On y trouve un lien entre ces problèmes et plusieurs classes de problèmes d’homomorphismes, dont la classe des Problèmes de Satisfaction de Contraintes. Le troisième chapitre concerne deux variantes lointaines du problème de domination, nommément les problèmes d’alliances globales dans un graphe pondéré et le problème de l’ensemble sûr. Le quatrième chapitre concerne la recherche d’une décomposition arborescente étoilée, c’est à dire une décomposition arborescente dont le rayon des sacs est 1. Enfin, le cinquième chapitre concerne une variante du problème de décider du comportement asymptotique de l’itéré du graphe des bicliques. / This thesis is about graph theory. Formally, a graph is a set of vertices and a set of edges, which are pair of vertices, linking vertices. This thesis deals with various decision problem linked to the notion of graph, and, for each of these problem, try to find its complexity class, or to give an algorithm. The first chapter is about the problem of finding the smallest connected tropical subgraph of a vertex-colored graph, which is the smallest connecter subgraph containing every colors. The second chapter is about problems of tropical homomorphism, a generalization of coloring problem. A link between these problems and several other class of homomorphism problems can be found in this chapter, especially with the class of Constraint Satisfaction Problem. The third chapter is about two variant of the domination problem, namely the global alliance problems in a weighted graph and the safe set problem. The fourth chapter is about the problem of finding a star tree-decomposition, which is a tree-decomposition where the radius of bags is 1. Finally, the fifth chapter is about a variant of the problem of deciding the asymptotic behavior of the iterated biclique graph

The generalized deBruijn graph dB(a, k) is the directed graph with a k vertices and edges between vertices x = a1, a 2, ... ak and y = b1, b2, ... b k precisely when a2, ... ak = b1, b2, ... bk-1. The deBruijn graphs can be further generalized by introducing an overlap variable t ≤ k - 1 where the number of consecutive digits by which the vertex labels (sequences) overlap is t. The α-overlap graph is the underlying simple graph of the generalized deBruijn digraph with vertex label overlap 0 < t ≤ k - 1.We denote the α-overlap graph by Gα = G(a, k, t) and the parameters a, k and t are positive integers such that a ≥ 2 and k > t > 0. Thus dB(a, k) = G(a, k, k - 1). In this paper, we show that every a-overlap graph is 3-colorable for any a if k is sufficiently large. We also determine bounds on the chromatic number of the α-overlap graphs if a is much larger than k.

A graph G is 2-stratified if its vertex set is partitioned into two nonempty classes (each of which is a stratum or a color class). We color the vertices in one color class red and the other color class blue. Let F be a 2-stratified graph with one fixed blue vertex v specified. We say that F is rooted at v. The F-domination number of a graph G is the minimum number of red vertices of G in a red-blue coloring of the vertices of G such that for every blue vertex v of G, there is a copy of F in G rooted at v. In this paper, we survey recent results on the F-domination number for various 2-stratified graphs F.

Let G be a nontrivial connected, edge-colored graph. An edge-cut R of G is called a rainbow cut if no two edges in R are colored the same. An edge-coloring of G is a rainbow disconnection coloring if for every two distinct vertices u and v of G, there exists a rainbow cut in G, where u and v belong to different components of G − R. We introduce and study the rainbow disconnection number rd(G) of G, which is defined as the minimum number of colors required of a rainbow disconnection coloring of G. It is shown that the rainbow disconnection number of a nontrivial connected graph G equals the maximum rainbow disconnection number among the blocks of G. It is also shown that for a nontrivial connected graph G of order n, rd(G) = n−1 if and only if G contains at least two vertices of degree n − 1. The rainbow disconnection numbers of all grids Pm Pn are determined. Furthermore, it is shown for integers k and n with 1 ≤ k ≤ n − 1 that the minimum size of a connected graph of order n having rainbow disconnection number k is n + k − 2. Other results and a conjecture are also presented.

Knot theory has rapidly expanded in recent years. New representations of braid groups led to an extremely powerful polynomial invariant, the Jones polynomial. Combinatorics applied to knot and link diagrams led to generalizations. Knot theory also has connections with other fields such as statistical mechanics and quantum field theory, and has applications in determining how certain enzymes act on DNA molecules, for example. The principal objective of this dissertation is to study the relations between knots and algebraic structures called quandles. A quandle is a set with a binary operation satisfying some properties related to the three Reidemeister moves. The study of quandles in relation to knot theory was intitiated by Joyce and Matveev. Later, racks and their (co)homology theory were defined by Fenn and Rourke. The rack (co)homology was also studied by Grana from the viewpoint of Hopf algebras. Furthermore, a modified definition of homology theory for quandles was introduced by Carter, Jelsovsky, Kamada, Langford, and Saito to define state-sum invariants for knots and knotted surfaces, called quandle cocycle invariants. This dissertation studies the quandle cocycle invariants using extensions of quandles and knot colorings. We obtain a coloring of a knot by assigning elements of a quandle to the arcs of the knot diagram. Such colorings are used to define knot invariants by state-sum. For a given coloring, a 2-cocycle is assigned at each crossing as the Boltzmann weight. The product of the weights over all crossings is the contribution to the state-sum, which is the formal summation of the contributions over all possible colorings of the given knot diagram by a given quandle. Generalizing the cocycle invariant for knots to links, we define two kinds of invariants for links: a component-wise invariant, and an invariant defined as families of vectors. Abelian extensions of quandles are also defined and studied. We give a formula for creating infinite families of abelian extensions of Alexander quandles. These extensions give rise to explicit formulas for computing 2-cocycles. The theory of quandle extensions parallels that of groups. Moreover, we investigate the notion of extending colorings of knots using quandle extensions. In particular, we show how the obstruction to extending the coloring contributes to the non-trivial terms of the cocycle invariants for knots and links. Moreover, we demonstrate the relation between these new cocycle invariants and Alexander matrices.

The object of this research was to prepare substituted derivatives of various chalcones having the nitro group substituted in the 31-position, the idea being to help complete the series of chalcones having the nitro group in that position. This was to be done by condensing various substituted benzaldehydes with m-nitroacetophenone, using dry hydrogen chloride as a condensing agent. The properties of the resulting chalcones were then to be determined by observing color reactions, spectra, and other general physical properties.

Regular graphs are graphs in which all vertices have the same degree. Many properties of these graphs are known. Such graphs play an important role in modeling network configurations where equipment limitations impose a restriction on the maximum number of links emanating from a node. These limitations do not enforce strict regularity, and it becomes interesting to investigate nonregular graphs that are in some sense close to regular. This dissertation explores a particular class of almost regular graphs in detail and defines generalizations on this class. A linear-time algorithm for the creation of arbitrarily large graphs of the discussed class is provided, and a polynomial-time algorithm for recognizing graphs in the class is given. Several invariants for the class are discussed. The edge-face chromatic number χef of a plane graph G is the minimum number of colors that must be assigned to the edges and faces of G such that no edge or face of G receives the same color as an edge or face with which it is incident or adjacent. A well-known result for the upper bound of χef exists for graphs with maximum degree Δ ≥ 10. We present a tight upper bound for plane graphs with Δ = 9.