Academic literature on the topic 'Packing chromatic number'

Graph coloring is an assignment of labels called colors to elements of a graph. The packing coloring was introduced by Goddard et al. [1] in 2008 which is a kind of coloring of a graph. This problem is NP-complete for general graphs. In this paper, we consider some transformation graphs and generalized their packing chromatic numbers.

Given a graph G, a function c : V(G) ?{1,..., k} with the property that for every u?v, c(u) = c(v) = i implies that the distance between u and v is greater than i, is called a k-packing coloring of G. The smallest integer k for which there exists a k-packing coloring of G is called the packing chromatic number of G, and is denoted by ??(G). Packing chromatic vertex-critical graphs are the graphs G for which ??(G ? x) < ??(G) holds for every vertex x of G. A graph G is called a packing chromatic critical graph if for every proper subgraph H of G, ??(H) < ??(G). Both of the mentioned variations of critical graphs with respect to the packing chromatic number have already been studied [6, 23]. All packing chromatic (vertex-)critical graphs G with ??(G) = 3 were characterized, while there were known only partial results for graphs G with ??(G) = 4. In this paper, we provide characterizations of all packing chromatic vertex-critical graphs G with ??(G) = 4 and all packing chromatic critical graphs G with ??(G) = 4.

Given a graph G and a positive integer i, an i-packing in G is a subset W of the vertex set of G such that the distance between any two distinct vertices from W is greater than i. The packing chromatic number of a graph G, ??(G), is the smallest integer k such that the vertex set of G can be partitioned into sets Vi, i ? {1,..., k}, where each Vi is an i-packing. In this paper, we present some general properties of packing chromatic numbers of finite super subdivisions of graphs. We determine the packing chromatic numbers of the finite super subdivisions of complete graphs, cycles and some neighborhood corona graphs.

The packing chromatic number χ_{p}(G) of a graph G = (V,E) is the smallest integer k such that the vertex set V(G) can be partitioned into disjoint classes V1 ,V2 ,...,Vk , where vertices in Vi have pairwise distance greater than i. In this paper, we compute the packing chromatic number of circulant graphs with different jump sizes._{}

Les deux problèmes majeurs considérés dans cette thèse : le b-coloration problème et le graphe emballage problème. 1. Le b-coloration problème : Une coloration des sommets de G s'appelle une b-coloration si chaque classe de couleur contient au moins un sommet qui a un voisin dans toutes les autres classes de couleur. Le nombre b-chromatique b(G) de G est le plus grand entier k pour lequel G a une b-coloration avec k couleurs. EL Sahili et Kouider demandent s'il est vrai que chaque graphe d-régulier G avec le périmètre au moins 5 satisfait b(G) = d + 1. Blidia, Maffray et Zemir ont montré que la conjecture d'El Sahili et de Kouider est vraie pour d ≤ 6. En outre, la question a été résolue pour les graphes d-réguliers dans des conditions supplémentaires. Nous étudions la conjecture d'El Sahili et de Kouider en déterminant quand elle est possible et dans quelles conditions supplémentaires elle est vrai. Nous montrons que b(G) = d + 1 si G est un graphe d-régulier qui ne contient pas un cycle d'ordre 4 ni d'ordre 6. En outre, nous fournissons des conditions sur les sommets d'un graphe d-régulier G sans le cycle d'ordre 4 de sorte que b(G) = d + 1. Cabello et Jakovac ont prouvé si v(G) ≥ 2d3 - d2 + d, puis b(G) = d + 1, où G est un graphe d-régulier. Nous améliorons ce résultat en montrant que si v(G) ≥ 2d3 - 2d2 + 2d alors b(G) = d + 1 pour un graphe d-régulier G. 2. Emballage de graphe problème : Soit G un graphe d'ordre n. Considérer une permutation σ : V (G) → V (Kn), la fonction σ* : E(G) → E(Kn) telle que σ *(xy) = σ *(x) σ *(y) est la fonction induite par σ. Nous disons qu'il y a un emballage de k copies de G (dans le graphe complet Kn) s'il existe k permutations σi : V (G) → V (Kn), où i = 1, …, k, telles que σi*(E(G)) ∩ σj (E(G)) = ɸ pour i ≠ j. Un emballage de k copies d'un graphe G est appelé un k-placement de G. La puissance k d'un graphe G, noté par Gk, est un graphe avec le même ensemble de sommets que G et une arête entre deux sommets si et seulement si le distance entre ces deux sommets est au plus k. Kheddouci et al. ont prouvé que pour un arbre non-étoile T, il existe un 2-placement σ sur V (T). Nous introduisons pour la première fois le problème emballage marqué de graphe dans son graphe puissance
Two problems are considered in this thesis: the b-coloring problem and the graph packing problem. 1. The b-Coloring Problem : A b-coloring of a graph G is a proper coloring of the vertices of G such that there exists a vertex in each color class joined to at least a vertex in each other color class. The b-chromatic number of a graph G, denoted by b(G), is the maximum number t such that G admits a b-coloring with t colors. El Sahili and Kouider asked whether it is true that every d-regular graph G with girth at least 5 satisfies b(G) = d + 1. Blidia, Maffray and Zemir proved that the conjecture is true for d ≤ 6. Also, the question was solved for d-regular graphs with supplementary conditions. We study El Sahili and Kouider conjecture by determining when it is possible and under what supplementary conditions it is true. We prove that b(G) = d+1 if G is a d-regular graph containing neither a cycle of order 4 nor of order 6. Then, we provide specific conditions on the vertices of a d-regular graph G with no cycle of order 4 so that b(G) = d + 1. Cabello and Jakovac proved that if v(G) ≥ 2d3 - d2 + d, then b(G) = d + 1, where G is a d-regular graph. We improve this bound by proving that if v(G) ≥ 2d3 - 2d2 + 2d, then b(G) = d+1 for a d-regular graph G. 2. Graph Packing Problem : Graph packing problem is a classical problem in graph theory and has been extensively studied since the early 70's. Consider a permutation σ : V (G) → V (Kn), the function σ* : E(G) → E(Kn) such that σ *(xy) = σ *(x) σ *(y) is the function induced by σ. We say that there is a packing of k copies of G into the complete graph Kn if there exist k permutations σ i : V (G) → V (Kn), where i = 1,…, k, such that σ*i (E(G)) ∩ σ*j (E(G)) = ɸ for I ≠ j. A packing of k copies of a graph G will be called a k-placement of G. The kth power Gk of a graph G is the supergraph of G formed by adding an edge between all pairs of vertices of G with distance at most k. Kheddouci et al. proved that for any non-star tree T there exists a 2-placement σ on V (T). We introduce a new variant of graph packing problem, called the labeled packing of a graph into its power graph

Cette thèse de doctorat est divisée en deux parties principales: La partie I explore l'existence de chemins orientés dans les digraphes, cherchant à établir un lien entre le nombre chromatique d'un digraphe et l'existence de chemins orientés spécifiques en tant que sous-digraphes. Les digraphes contenus dans n'importe quel digraphe n-chromatique sont appelés n-universels. Nous examinons deux conjectures : la conjecture de Burr, qui affirme que chaque arbre orienté d'ordre n est (2n-2)-universel, et la conjecture d'El Sahili, qui déclare que chaque chemin orienté d'ordre n est n-universel. Pour les chemins orientés en général, la meilleure borne est donnée par Burr, à savoir que chaque chemin orienté d'ordre n est (n - 1)²-universel.Notre objectif est d'étudier des chemins à trois blocs. Pour atteindre nos objectifs, nous nous appuyons fortement sur des concepts fondamentaux, y compris l'induction sur l'ordre d'un digraphe donné, les forêts finales, les techniques de nivellement et les méthodes de décomposition stratégique de digraphes. Un chemin comportant trois blocs est désigné par P(k1, k2, k3). Pour le chemin P(k,1,l), nous avons confirmé la conjecture d'El Sahili dans les digraphes Hamiltoniens. En se basant sur ce résultat pour les digraphes Hamiltoniens, nous avons confirmé la conjecture d'El Sahili pour une classe plus générale de digraphes, ceux qui incluent un chemin dirigé hamiltonien. Nous introduisons une technique novatrice : une décomposition du digraphe en sous-digraphes résultant d'une série d'opérations basées sur le fameux théorème de Roy, qui garantit l'existence d'un chemin orienté dirigé d'ordre n dans tout digraphe n-chromatique. Cette technique s'est avérée cruciale pour établir de nouvelles bornes linéaires pour le nombre chromatique de digraphes qui ne comportent pas de chemin orienté avec trois blocs. En effet, en utilisant cette technique, nous avons prouvé que le chemin P(k,1,l) satisfait la conjecture de Burr. De plus, pour n'importe quel chemin à trois blocs, P(k,l,r), nous avons établi une borne linéaire pour le nombre chromatique qui améliore toutes les bornes précédemment atteintes. Dans la partie II, nous étudions le problème de la coloration de packing dans les graphes. Étant donnée une séquence non décroissante S = (s1, s2, . . . , sk) d'entiers positifs, une S-coloration (de packing) d'un graphe G est une partition de l'ensemble des sommets de G en k sous-ensembles {V1, V2, . . . , Vk} tels que pour chaque 1 ≤ i ≤ k, la distance entre deux sommets distincts u et v dans Vi est d'au moins si + 1. Notre attention est centrée sur une conjecture intrigante proposée par Brešar et al., qui affirme que l'arête subdivision de n'importe quel graphe subcubique admet une (1,2,3,4,5)-coloration de packing. Notre objectif est de confirmer cette conjecture pour des classes spécifiques de graphes subcubiques et de traiter les questions non résolues soulevées dans ce domaine. Une observation de Gastineau et Togni indique que si un graphe G est (1, 1, 2, 2)-colorable, alors son graphe subdivisé S(G) est (1,2,3,4,5)-colorable, et donc il satisfait la conjecture. En nous basant sur cette observation et afin de prouver la véracité de la conjecture pour la classe des graphes de Halin cubiques, nous avons étudié leur S-coloration de packing visant à prouver qu'ils admettent une coloration en (1, 1, 2, 2). Nous avons prouvé que tout graphe de Halin cubique est (1, 1, 2, 3)-colorable, et donc (1, 1, 2, 2)-colorable, et ainsi nous confirmons la conjecture pour cette classe. De plus, Gastineau et Togni, après avoir prouvé que chaque graphe subcubique est (1, 2, 2, 2, 2, 2, 2)-colorable, ont posé un problème ouvert sur le fait de savoir si chaque graphe subcubique est (1, 2, 2, 2, 2, 2)-colorable. Nous répondons affirmativement à cette question dans la classe particulière sur laquelle nous avons travaillé : nous avons prouvé que les graphes d'Halin cubiques sont (1, 2, 2, 2, 2, 2)-colorables
This PhD thesis is divided into two principal parts: Part I delves into the existenceof oriented paths in digraphs, aiming to establish a connection between a digraph'schromatic number and the existence of specific oriented paths within it as subdigraphs. Digraphs contained in any n-chromatic digraph are called n-universal. We consider two conjectures: Burr's conjecture, which states that every oriented tree of order n is (2n-2)-universal, and El Sahili's conjeture which states that every oriented path of order n is n-universal. For oriented paths in general, the best bound is given by Burr, that is every oriented path of order n is (n − 1)^2-universal. Our objective is to study the existence of an integer k such that any digraph with a chromatic number k, contains a copy of a given oriented path with three blocks as its subdigraph. To achieve our goals, we rely significantly on fundamental concepts, including, induction on the order of a given digraph, final forests, leveling techniques, and strategic digraph decomposition methods. A path P (k1, k2, k3) is an oriented path consisting of k1 forward arcs, followed by k2 backward arcs, and then by k3 forward arcs. For the path P(k,1,l), we have confirmed El Sahili's conjecture in Hamiltonian digraphs. More clearly, we have established the existence of any path P (k, 1, l) of order n in any n-chromatic Hamiltonian digraph. And depending on this result concerning Hamiltonian digraphs, we proved the correctness of El Sahili's conjecture on a more general class of digraphs which is digraphs containing a Hamiltonian directed path. We introduce a new technique which is represented by a decomposition of the digraph into subdigraphs defined by a series of successive operations applied to the digraph relying on the famous theorem of Roy which establishes the existence of a directed path of order n in any n-chromatic digraph. This technique has proven to be instrumental in establishing new linear bounds for the chromatic number of digraphs that lack an oriented path with three blocks. In deed, using this technique, we proved that the path P(k,1,l) satisfies Burr's conjecture.Moreover, for any path with three blocks, P(k,l,r) we establish a linear bound for the chromatic number which improves all the previously reached bounds. In Part II we study the problem of S-packing coloring in graphs. Given a non-decreasing sequence S = (s1, s2, . . . , sk) of positive integers, an S-packing coloring of a graph G is a partition of the vertex set of G into k subsets{V1, V2, . . . , Vk} such that for each 1 ≤ i ≤ k, the distance between any two dis-tinct vertices u and v in Vi is at least si + 1. Our focus is centered on an intriguing conjecture proposed by Brešar et al., which states that packing chromatic number of the subdivision of any subcubic graph is at most 5. Our desired aim is to provide a confirmation of this conjecture for specific classes of subcubic graphs, and to address the unresolved issues raised within this subject matter. An observation for Gastineau and Togni states that if a graph G is (1, 1, 2, 2)-packing colorable, then the chromatic number of its subdivision graph S(G) is at most 5, and hence it satisfies the conjecture. Depending on this observation, and in order to prove the correctness of the conjecture for the class of cubic Halin graphs, we studied its S-packing coloring aiming to prove that it admits a (1, 1, 2, 2)- packing coloring. We proved that a cubic Halin graph is (1, 1, 2, 3)-packing colorable, then it is (1, 1, 2, 2)-packing colorable, and so we confirm the conjecture for this class. Moreover, Gastineau and Togni, after proving that every subcubic graph is (1, 2, 2, 2, 2, 2, 2)-packing colorbale, have posed an open problem on whether every subcubic graph is (1, 2, 2, 2, 2, 2)-packing colorable. We answer this question in affirmative in the particular class we worked on; we proved that cubic Halin graphs are (1, 2, 2, 2, 2, 2)-packing colorable

Un graphe métrique G(X;D) est un graphe dont l’ensemble des sommets est l’ensemble X des points d’un espace métrique (X; d), et dont les arêtes relient les paires fx; yg de sommets telles que d(x; y) 2 D. Dans cette thèse, nous considérons deux problèmes qui peuvent être interprétés comme des problèmes de graphes métriques dans Rn. Premièrement, nous nous intéressons au célèbre problème d’empilements de sphères, relié au graphe métrique G(Rn; ]0; 2r[) pour un rayon de sphère r donné. Récemment, Venkatesh a amélioré d’un facteur log log n la meilleure borne inférieure connue pour un empilement de sphères donné par un réseau, pour une suite infinie de dimensions n. Ici nous prouvons une version effective de ce résultat, dans le sens où l’on exhibe, pour la même suite de dimensions, des familles finies de réseaux qui contiennent un réseaux dont la densité atteint la borne de Venkatesh. Notre construction met en jeu des codes construits sur des corps cyclotomiques, relevés en réseaux grâce à un analogue de la Construction A. Nous prouvons aussi un résultat similaire pour des familles de réseaux symplectiques. Deuxièmement, nous considérons le graphe distance-unité G associé à une norme k_k. Le nombre m1 (Rn; k _ k) est défini comme le supremum des densités réalisées par les stables de G. Si la boule unité associée à k _ k pave Rn par translation, alors il est aisé de voir que m1 (Rn; k _ k) > 1 2n . C. Bachoc et S. Robins ont conjecturé qu’il y a égalité. On montre que cette conjecture est vraie pour n = 2 ainsi que pour des régions de Voronoï de plusieurs types de réseaux en dimension supérieure, ceci en se ramenant à la résolution de problèmes d’empilement dans des graphes discrets
A distance graph G(X;D) is a graph whose set of vertices is the set of points X of a metric space (X; d), and whose edges connect the pairs fx; yg such that d(x; y) 2 D. In this thesis, we consider two problems that may be interpreted in terms of distance graphs in Rn. First, we study the famous sphere packing problem, in relation with thedistance graph G(Rn; (0; 2r)) for a given sphere radius r. Recently, Venkatesh improved the best known lower bound for lattice sphere packings by a factor log log n for infinitely many dimensions n. We prove an effective version of this result, in the sense that we exhibit, for the same set of dimensions, finite families of lattices containing a lattice reaching this bound. Our construction uses codes over cyclotomic fields, lifted to lattices via Construction A. We also prove a similar result for families of symplectic lattices. Second, we consider the unit distance graph G associated with a norm k _ k. The number m1 (Rn; k _ k) is defined as the supremum of the densities achieved by independent sets in G. If the unit ball corresponding with k _ k tiles Rn by translation, then it is easy to see that m1 (Rn; k _ k) > 1 2n . C. Bachoc and S. Robins conjectured that the equality always holds. We show that this conjecture is true for n = 2 and for several Voronoï cells of lattices in higher dimensions, by solving packing problems in discrete graphs

The entropy of a graph is a functional depending both on the graph itself and on a probability distribution on its vertex set. This graph functional originated from the problem of source coding in information theory and was introduced by J. K\"{o}rner in 1973. Although the notion of graph entropy has its roots in information theory, it was proved to be closely related to some classical and frequently studied graph theoretic concepts. For example, it provides an equivalent definition for a graph to be perfect and it can also be applied to obtain lower bounds in graph covering problems. In this thesis, we review and investigate three equivalent definitions of graph entropy and its basic properties. Minimum entropy colouring of a graph was proposed by N. Alon in 1996. We study minimum entropy colouring and its relation to graph entropy. We also discuss the relationship between the entropy and the fractional chromatic number of a graph which was already established in the literature. A graph $G$ is called \emph{symmetric with respect to a functional $F_G(P)$} defined on the set of all the probability distributions on its vertex set if the distribution $P^*$ maximizing $F_G(P)$ is uniform on $V(G)$. Using the combinatorial definition of the entropy of a graph in terms of its vertex packing polytope and the relationship between the graph entropy and fractional chromatic number, we prove that vertex transitive graphs are symmetric with respect to graph entropy. Furthermore, we show that a bipartite graph is symmetric with respect to graph entropy if and only if it has a perfect matching. As a generalization of this result, we characterize some classes of symmetric perfect graphs with respect to graph entropy. Finally, we prove that the line graph of every bridgeless cubic graph is symmetric with respect to graph entropy.

AbstractA packing k-coloring is a natural variation on the standard notion of graph k-coloring, where vertices are assigned numbers from $$\{1, \ldots , k\}$$ { 1 , … , k } , and any two vertices assigned a common color $$c \in \{1, \ldots , k\}$$ c ∈ { 1 , … , k } need to be at a distance greater than c (as opposed to 1, in standard graph colorings). Despite a sequence of incremental work, determining the packing chromatic number of the infinite square grid has remained an open problem since its introduction in 2002. We culminate the search by proving this number to be 15. We achieve this result by improving the best-known method for this problem by roughly two orders of magnitude. The most important technique to boost performance is a novel, surprisingly effective propositional encoding for packing colorings. Additionally, we developed an alternative symmetry breaking method. Since both new techniques are more complex than existing techniques for this problem, a verified approach is required to trust them. We include both techniques in a proof of unsatisfiability, reducing the trusted core to the correctness of the direct encoding.

Abstract The HMG-box is a new kind of eukaryotic protein domain involved in DNA binding. It has been discovered in a number of chromatin proteins, general transcription factors, and transcriptional regulators which control tissue differentiation and sex determination. The most unusual feature of HMG-boxes is that they recognise and/ or produce primarily conformational features in DNA, even if some members of this family can also bind sequence-specifically to particular sites on linear DNA. The diverse set of HMG-box-containing proteins (which we will call ‘HMG-box proteins’ from now on) appear to be involved in a broad spectrum of DNA transactions, ranging from transcription to DNA packaging in chromatin. Such versatility is uncommon and suggests that the ability of HMG-boxes to manipulate DNA can be used in similar ways in highly different functional contexts.