Academic literature on the topic 'Coloriage de graphe'
Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles
Consult the lists of relevant articles, books, theses, conference reports, and other scholarly sources on the topic 'Coloriage de graphe.'
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.
Journal articles on the topic "Coloriage de graphe"
1
Bagheri Gh., Behrooz, and Behnaz Omoomi. "On the simultaneous edge coloring of graphs." Discrete Mathematics, Algorithms and Applications 06, no. 04 (October 10, 2014): 1450049. http://dx.doi.org/10.1142/s1793830914500499.
Full textAbstract:
A μ-simultaneous edge coloring of graph G is a set of μ proper edge colorings of G with a same color set such that for each vertex, the sets of colors appearing on the edges incident to that vertex are the same in each coloring and no edge receives the same color in any two colorings. The μ-simultaneous edge coloring of bipartite graphs has a close relation with μ-way Latin trades. Mahdian et al. (2000) conjectured that every bridgeless bipartite graph is 2-simultaneous edge colorable. Luo et al. (2004) showed that every bipartite graphic sequence S with all its elements greater than one, has a realization that admits a 2-simultaneous edge coloring. In this paper, the μ-simultaneous edge coloring of graphs is studied. Moreover, the properties of the extremal counterexample to the above conjecture are investigated. Also, a relation between 2-simultaneous edge coloring of a graph and a cycle double cover with certain properties is shown and using this relation, some results about 2-simultaneous edge colorable graphs are obtained.
2
Abhishek, Kumar. "Strongly set-colorable graphs." Discrete Mathematics, Algorithms and Applications 11, no. 01 (February 2019): 1950007. http://dx.doi.org/10.1142/s1793830919500071.
Full textAbstract:
In [S. M. Hegde, Set colorings of graphs, European J. Combin. 30 (2009) 986–995.] Hegde introduced the notion of set colorings of a graph [Formula: see text] as an assignment of distinct subsets of a finite set [Formula: see text] of [Formula: see text] colors to the vertices of [Formula: see text] such that all the colors of the edges which are obtained as the symmetric differences of the subsets assigned to their end-vertices are distinct. Additionally, if all the sets on the vertices and edges of [Formula: see text] are the set of all nonempty subsets of [Formula: see text] then the coloring is said to be a strong set-coloring and [Formula: see text] is said to be strongly set-colorable. In this paper, we report some new necessary conditions and propose a conjuncture for the sufficient condition for a graph to admit strong set-coloring. We also identify and characterize some new classes of graphs admitting strong set-coloring. In addition to these, we also propose strategies to construct infinite families graphs admitting strong set-coloring.
3
Erzurumluoğlu, Aras, and C. A. Rodger. "On Evenly-Equitable, Balanced Edge-Colorings and Related Notions." International Journal of Combinatorics 2015 (March 4, 2015): 1–7. http://dx.doi.org/10.1155/2015/201427.
Full textAbstract:
A graph G is said to be even if all vertices of G have even degree. Given a k-edge-coloring of a graph G, for each color i∈Zk={0,1,…,k-1} let G(i) denote the spanning subgraph of G in which the edge-set contains precisely the edges colored i. A k-edge-coloring of G is said to be an even k-edge-coloring if for each color i∈Zk, G(i) is an even graph. A k-edge-coloring of G is said to be evenly-equitable if for each color i∈Zk, G(i) is an even graph, and for each vertex v∈V(G) and for any pair of colors i,j∈Zk, |degG(i)(v)-degG(j)(v)|∈{0,2}. For any pair of vertices {v,w} let mG({v,w}) be the number of edges between v and w in G (we allow v=w, where {v,v} denotes a loop incident with v). A k-edge-coloring of G is said to be balanced if for all pairs of colors i and j and all pairs of vertices v and w (possibly v=w), |mG(i)({v,w})-mG(j)({v,w})|≤1. Hilton proved that each even graph has an evenly-equitable k-edge-coloring for each k∈N. In this paper we extend this result by finding a characterization for graphs that have an evenly-equitable, balanced k-edge-coloring for each k∈N. Correspondingly we find a characterization for even graphs to have an evenly-equitable, balanced 2-edge-coloring. Then we give an instance of how evenly-equitable, balanced edge-colorings can be used to determine if a certain fairness property of factorizations of some regular graphs is satisfied. Finally we indicate how different fairness notions on edge-colorings interact with each other.
4
Dobrinen, Natasha. "The Ramsey theory of the universal homogeneous triangle-free graph." Journal of Mathematical Logic 20, no. 02 (January 28, 2020): 2050012. http://dx.doi.org/10.1142/s0219061320500129.
Full textAbstract:
The universal homogeneous triangle-free graph, constructed by Henson [A family of countable homogeneous graphs, Pacific J. Math. 38(1) (1971) 69–83] and denoted [Formula: see text], is the triangle-free analogue of the Rado graph. While the Ramsey theory of the Rado graph has been completely established, beginning with Erdős–Hajnal–Posá [Strong embeddings of graphs into coloured graphs, in Infinite and Finite Sets. Vol.[Formula: see text] , eds. A. Hajnal, R. Rado and V. Sós, Colloquia Mathematica Societatis János Bolyai, Vol. 10 (North-Holland, 1973), pp. 585–595] and culminating in work of Sauer [Coloring subgraphs of the Rado graph, Combinatorica 26(2) (2006) 231–253] and Laflamme–Sauer–Vuksanovic [Canonical partitions of universal structures, Combinatorica 26(2) (2006) 183–205], the Ramsey theory of [Formula: see text] had only progressed to bounds for vertex colorings [P. Komjáth and V. Rödl, Coloring of universal graphs, Graphs Combin. 2(1) (1986) 55–60] and edge colorings [N. Sauer, Edge partitions of the countable triangle free homogenous graph, Discrete Math. 185(1–3) (1998) 137–181]. This was due to a lack of broadscale techniques. We solve this problem in general: For each finite triangle-free graph [Formula: see text], there is a finite number [Formula: see text] such that for any coloring of all copies of [Formula: see text] in [Formula: see text] into finitely many colors, there is a subgraph of [Formula: see text] which is again universal homogeneous triangle-free in which the coloring takes no more than [Formula: see text] colors. This is the first such result for a homogeneous structure omitting copies of some nontrivial finite structure. The proof entails developments of new broadscale techniques, including a flexible method for constructing trees which code [Formula: see text] and the development of their Ramsey theory.
5
Fekete, Sándor P., and Phillip Keldenich. "Conflict-Free Coloring of Intersection Graphs." International Journal of Computational Geometry & Applications 28, no. 03 (September 2018): 289–307. http://dx.doi.org/10.1142/s0218195918500085.
Full textAbstract:
A conflict-free[Formula: see text]-coloring of a graph [Formula: see text] assigns one of [Formula: see text] different colors to some of the vertices such that, for every vertex [Formula: see text], there is a color that is assigned to exactly one vertex among [Formula: see text] and [Formula: see text]’s neighbors. Such colorings have applications in wireless networking, robotics, and geometry, and are well studied in graph theory. Here we study the conflict-free coloring of geometric intersection graphs. We demonstrate that the intersection graph of [Formula: see text] geometric objects without fatness properties and size restrictions may have conflict-free chromatic number in [Formula: see text] and in [Formula: see text] for disks or squares of different sizes; it is known for general graphs that the worst case is in [Formula: see text]. For unit-disk intersection graphs, we prove that it is NP-complete to decide the existence of a conflict-free coloring with one color; we also show that six colors always suffice, using an algorithm that colors unit disk graphs of restricted height with two colors. We conjecture that four colors are sufficient, which we prove for unit squares instead of unit disks. For interval graphs, we establish a tight worst-case bound of two.
6
Naduvath, Sudev. "Equitable coloring parameters of certain graph classes." Discrete Mathematics, Algorithms and Applications 10, no. 03 (June 2018): 1850040. http://dx.doi.org/10.1142/s1793830918500404.
Full textAbstract:
Coloring the vertices of a graph [Formula: see text] subject to given conditions can be considered as a random experiment and corresponding to this experiment, a discrete random variable [Formula: see text] can be defined as the color of a vertex chosen at random, with respect to the given type of coloring of [Formula: see text] and a probability mass function for this random variable can be defined accordingly. A proper coloring [Formula: see text] of a graph [Formula: see text], which assigns colors to the vertices of [Formula: see text] such that the numbers of vertices in any two color classes differ by at most one, is called an equitable coloring of [Formula: see text]. In this paper, we study two statistical parameters of certain graphs, with respect to their equitable colorings.
7
Bhakta, Prateek, Benjamin Brett Buckner, Lauren Farquhar, Vikram Kamat, Sara Krehbiel, and Heather M. Russell. "Cut-Colorings in Coloring Graphs." Graphs and Combinatorics 35, no. 1 (November 28, 2018): 239–48. http://dx.doi.org/10.1007/s00373-018-1985-6.
Full text
8
Sotskov, Yuri N. "Mixed Graph Colorings: A Historical Review." Mathematics 8, no. 3 (March 9, 2020): 385. http://dx.doi.org/10.3390/math8030385.
Full textAbstract:
This paper presents a historical review and recent developments in mixed graph colorings in the light of scheduling problems with the makespan criterion. A mixed graph contains both a set of arcs and a set of edges. Two types of colorings of the vertices of the mixed graph and one coloring of the arcs and edges of the mixed graph have been considered in the literature. The unit-time scheduling problem with the makespan criterion may be interpreted as an optimal coloring of the vertices of a mixed graph, where the number of used colors is minimum. Complexity results for optimal colorings of the mixed graph are systematized. The published algorithms for finding optimal mixed graph colorings are briefly surveyed. Two new colorings of a mixed graph are introduced.
9
KIM, DONG HAN, and SEONHEE LIM. "Subword complexity and Sturmian colorings of regular trees." Ergodic Theory and Dynamical Systems 35, no. 2 (August 13, 2013): 461–81. http://dx.doi.org/10.1017/etds.2013.50.
Full textAbstract:
AbstractIn this article, we discuss subword complexity of colorings of regular trees. We characterize colorings of bounded subword complexity and study Sturmian colorings, which are colorings of minimal unbounded subword complexity. We classify Sturmian colorings using their type sets. We show that any Sturmian coloring is a lifting of a coloring on a quotient graph of the tree which is a geodesic or a ray, with loops possibly attached, thus a lifting of an ‘infinite word’. We further give a complete characterization of the quotient graph for eventually periodic colorings.
10
Kaveh, Kamran, Alex McAvoy, Krishnendu Chatterjee, and Martin A. Nowak. "The Moran process on 2-chromatic graphs." PLOS Computational Biology 16, no. 11 (November 5, 2020): e1008402. http://dx.doi.org/10.1371/journal.pcbi.1008402.
Full textAbstract:
Resources are rarely distributed uniformly within a population. Heterogeneity in the concentration of a drug, the quality of breeding sites, or wealth can all affect evolutionary dynamics. In this study, we represent a collection of properties affecting the fitness at a given location using a color. A green node is rich in resources while a red node is poorer. More colors can represent a broader spectrum of resource qualities. For a population evolving according to the birth-death Moran model, the first question we address is which structures, identified by graph connectivity and graph coloring, are evolutionarily equivalent. We prove that all properly two-colored, undirected, regular graphs are evolutionarily equivalent (where “properly colored” means that no two neighbors have the same color). We then compare the effects of background heterogeneity on properly two-colored graphs to those with alternative schemes in which the colors are permuted. Finally, we discuss dynamic coloring as a model for spatiotemporal resource fluctuations, and we illustrate that random dynamic colorings often diminish the effects of background heterogeneity relative to a proper two-coloring.
Dissertations / Theses on the topic "Coloriage de graphe"
1
Legay, Sylvain. "Quelques problèmes d'algorithmique et combinatoires en théorie des grapphes." Thesis, Université Paris-Saclay (ComUE), 2017. http://www.theses.fr/2017SACLS030/document.
Full textAbstract:
Le sujet de cette thèse est la théorie des graphes. Formellement, un graphe est un ensemble de sommets et un ensemble d’arêtes, c’est à dire de paires de sommets, qui relient les sommets. Cette thèse traite de différents problèmes de décisions binaires ou de minimisations liés à la notion de graphe, et cherche, pour chacun de ces problèmes, à déterminer sa classe de complexité, ou à fournir un algorithme. Le premier chapitre concerne le problème de trouver le plus petit sous-graphe connexe tropical dans un graphe sommet-colorié, c’est à dire le plus petit sous-graphe connexe contenant toutes les couleurs. Le deuxième chapitre concerne les problèmes d’homomorphisme tropical, une généralisation des problèmes de coloriage de graphe. On y trouve un lien entre ces problèmes et plusieurs classes de problèmes d’homomorphismes, dont la classe des Problèmes de Satisfaction de Contraintes. Le troisième chapitre concerne deux variantes lointaines du problème de domination, nommément les problèmes d’alliances globales dans un graphe pondéré et le problème de l’ensemble sûr. Le quatrième chapitre concerne la recherche d’une décomposition arborescente étoilée, c’est à dire une décomposition arborescente dont le rayon des sacs est 1. Enfin, le cinquième chapitre concerne une variante du problème de décider du comportement asymptotique de l’itéré du graphe des bicliquesThis thesis is about graph theory. Formally, a graph is a set of vertices and a set of edges, which are pair of vertices, linking vertices. This thesis deals with various decision problem linked to the notion of graph, and, for each of these problem, try to find its complexity class, or to give an algorithm. The first chapter is about the problem of finding the smallest connected tropical subgraph of a vertex-colored graph, which is the smallest connecter subgraph containing every colors. The second chapter is about problems of tropical homomorphism, a generalization of coloring problem. A link between these problems and several other class of homomorphism problems can be found in this chapter, especially with the class of Constraint Satisfaction Problem. The third chapter is about two variant of the domination problem, namely the global alliance problems in a weighted graph and the safe set problem. The fourth chapter is about the problem of finding a star tree-decomposition, which is a tree-decomposition where the radius of bags is 1. Finally, the fifth chapter is about a variant of the problem of deciding the asymptotic behavior of the iterated biclique graph
2
Xu, Renyu. "Quelques problèmes de coloration du graphe." Thesis, Université Paris-Saclay (ComUE), 2017. http://www.theses.fr/2017SACLS104/document.
Full textAbstract:
Un k-coloriage total d'un graphe G est un coloriage de V(G)cup E(G) utilisant (1,2,…,k) couleurs tel qu'aucune paire d'éléments adjacents ou incidents ne reçoivent la même couleur. Le nombre chromatique total chi''(G) est le plus petit entier k tel que G admette un k-coloriage total. Dans le chapitre 2, nous étudions la coloration totale de graphe planaires et obtenons 3 résultats : (1) Soit G un graphe planaire avec pour degré maximum Deltageq8. Si toutes les paires de 6-cycles cordaux ne sont pas adjacentes dans G, alors chi''(G)=Delta+1. (2) Soit G un graphe planaire avec pour degré maximum Deltageq8. Si tout 7-cycle de G contient au plus deux cordes, alors chi''(G)=Delta+1. (3) Soit G un graphe planaire sans 5-cycles cordaux qui s'intersectent, c'est à dire tel que tout sommet ne soit incident qu'à au plus un seul 5-cycle cordal. Si Deltageq7, alors chi''(G)=Delta+1.Une relation L est appelé assignation pour un graphe G s'il met en relation chaque x à une liste de couleur. S'il est possible de colorier G tel que la couleur de chaque x soit présente dans la liste qu'il lui a été assignée, et qu'aucune paire de sommets adjacents n'aient la même couleur, alors on dit que G est L-coloriable. Un graphe G est k-selectionable si G est L-coloriable pour toute assignation L de G qui satisfait |L(v)geq k| pour tout x. Nous démontrons que si chaque 5-cycle de G n'est pas simultanément adjacent à des 3-cycles et des 4-cycles, alors G est 4-sélectionable. Dans le chapitre 3, nous prouvons que si aucun des 5-cycles de G n'est adjacent à un 4-cycles, alors chi'_l(G)=Delta et chi''_l(G)=Delta+1 si Delta(G)geq8, et chi'_l(G)leqDelta+1 et chi''_l(G)leqDelta+2 si Delta(G)geq6.Dans le chapitre 4, nous allons fournir une définition du coloriage total somme-des-voisins-distinguant, et passer en revue les progrgrave{e}s et conjecture concernant ce type de coloriage. Soit f(v) la somme des couleurs d'un sommet v et des toutes les arrêtes incidentes à v. Un k-coloriage total somme-des-voisins-distinguant de G est un k coloriage total de G tel que pour chaque arrête uvin E(G), f(u)eq f(v). Le plus petit k tel qu'on ai un tel coloriage sur G est appelé le nombre chromatique total somme-des-voisins-distinguant, noté chi''_{sum} (G). Nous avons démontré que si un graphe G avec degré maximum Delta(G) peut être embedded dans une surface Sigma de caractéristique eulérienne chi(Sigma)geq0, alors chi_{sum}^{''}(G)leq max{Delta(G)+2, 16}.Une forêt linéaire est un graphe pour lequel chaque composante connexe est une chemin. L'arboricité linéaire la(G) d'un graphe G tel que définie est le nombre minimum de forêts linéaires dans G, dont l'union est égale à V(G). Dans le chapitre 5, nous prouvons que si G est une graphe planaire tel que tout 7-cycle de G contienne au plus deux cordes, alors G est linéairementleft lceil frac{Delta+1}{2}ightceil-sélectionable si Delta(G)geq6, et G est linéairement left lceil frac{Delta}{2}ightceil-sélectionable si Delta(G)geq 11A k-total-coloring of a graph G is a coloring of V(G)cup E(G) using (1,2,…,k) colors such that no two adjacent or incident elements receive the same color．The total chromatic number chi''(G) is the smallest integer k such that G has a k-total-coloring. In chapter 2, we study total coloring of planar graphs and obtain three results: (1) Let G be a planar graph with maximum degree Deltageq8. If every two chordal 6-cycles are not adjacent in G, then chi''(G)=Delta+1. (2) Let G be a planar graph G with maximum degree Deltageq8. If any 7-cycle of G contains at most two chords, then chi''(G)=Delta+1. (3) Let G be a planar graph without intersecting chordal 5-cycles, that is, every vertex is incident with at most one chordal 5-cycle. If Deltageq7, then chi''(G)=Delta+1.A mapping L is said to be an assignment for a graph G if it assigns a list L(x) of colors to each xin V(G)cup E(G). If it is possible to color G so that every vertex gets a color from its list and no two adjacent vertices receive the same color, then we say that G is L-colorable. A graph G is k-choosable if G is an L-colorable for any assignment L for G satisfying |L(x)|geq k for every vertex xin V(G)cup E(G). We prove that if every 5-cycle of G is not simultaneously adjacent to 3-cycles and 4-cycles, then G is 4-choosable. In chapter 3, if every 5-cycles of G is not adjacent to 4-cycles, we prove that chi'_l(G)=Delta, chi''_l(G)=Delta+1 if Delta(G)geq8, and chi'_l(G)leqDelta+1, chi''_l(G)leqDelta+2 if Delta(G)geq6.In chapter 4, we will give the definition of neighbor sum distinguishing total coloring. Let f(v) denote the sum of the colors of a vertex v and the colors of all incident edges of v. A total k-neighbor sum distinguishing-coloring of G is a total k-coloring of G such that for each edge uvin E(G), f(u)eq f(v). The smallestnumber k is called the neighbor sum distinguishing total chromatic number, denoted by chi''_{sum} (G). Pilsniak and Wozniak conjectured that for any graph G with maximum degree Delta(G) holds that chi''_{sum} (G)leqDelta(G)+3. We prove for a graph G with maximum degree Delta(G) which can be embedded in a surface Sigma of Euler characteristic chi(Sigma)geq0, then chi_{sum}^{''}(G)leq max{Delta(G)+2, 16}.Lastly, we study the linear L-choosable arboricity of graph. A linear forest is a graph in which each component is a path. The linear arboricity la(G) of a graph G is the minimum number of linear forests in G, whose union is the set of all edges of G. A list assignment L to the edges of G is the assignment of a set L(e)subseteq N of colors to every edge e of G, where N is the set of positive integers. If G has a coloring varphi (e) such that varphi (e)in L(e) for every edge e and (V(G),varphi^{-1}(i)) is a linear forest for any iin C_{varphi}, where C_{varphi }=left { varphi (e)|ein E(G)ight }, then we say that G is linear L-colorable and varphi is a linear L-coloring of G. We say that G is linear k-choosable if it is linear L-colorable for every list assignment L satisfying |L(e)| geq k for all edges e. The list linear arboricity la_{list}(G) of a graph G is the minimum number k for which G is linear k-list colorable. It is obvious that la(G)leq la_{list}(G). In chapter 5, we prove that if G is a planar graph such that every 7-cycle of G contains at most two chords, then G is linear left lceil frac{Delta+1}{2}ightceil-choosable if Delta(G)geq6, and G is linear left lceil frac{Delta}{2}ightceil-choosable if Delta(G)geq 11
3
Pastor, Lucas. "Coloration, ensemble indépendant et structure de graphe." Thesis, Université Grenoble Alpes (ComUE), 2017. http://www.theses.fr/2017GREAM071/document.
Full textAbstract:
Cette thèse traite de la coloration de graphe, de la coloration par liste,d'ensembles indépendants de poids maximum et de la théorie structurelle des graphes.Dans un premier temps, nous fournissons un algorithme s'exécutant en temps polynomial pour le problème de la 4-coloration dans des sous-classes de graphe sans $P_6$. Ces algorithmes se basent sur une compréhension précise de la structure de ces classes de graphes, pour laquelle nous donnons une description complète.Deuxièmement, nous étudions une conjecture portant sur la coloration par liste et prouvons que pour tout graphe parfait sans griffe dont la taille de la plus grande clique est bornée par 4, le nombre chromatique est égal au nombre chromatique par liste. Ce résultat est obtenu en utilisant un théorème de décomposition des graphes parfaits sans griffe, une description structurelle des graphes de base de cette décomposition et le célèbre théorème de Galvin.Ensuite, en utilisant la description structurelle élaborée dans le premier chapitre et en renforçant certains aspects de celle-ci, nous fournissons un algorithme s'exécutant en temps polynomial pour le problème d'indépendant de poids maximum dans des sous-classes de graphe sans $P_6$ et sans $P_7$. Dans le dernier chapitre de ce manuscrit, nous infirmons une conjecture datant de 1999 de De Simone et K"orner sur les graphes normaux. Notre preuve est probabiliste et est obtenue en utilisant les graphes aléatoiresThis thesis deals with graph coloring, list-coloring, maximum weightstable set (shortened as MWSS) and structural graph theory.First, we provide polynomial-time algorithms for the 4-coloring problem insubclasses of $P_6$-free graphs. These algorithms rely on a preciseunderstanding of the structure of these classes of graphs for which we give afull description.Secondly, we study the list-coloring conjecture and prove that for anyclaw-free perfect graph with clique number bounded by 4, the chromatic numberand the choice number are equal. This result is obtained by using adecomposition theorem for claw-free perfect graphs, a structural description ofthe basic graphs of this decomposition and by using Galvin's famous theorem.Next by using the structural description given in the first chapter andstrengthening other aspects of this structure, we provide polynomial-timealgorithms for the MWSS problem in subclasses of $P_6$-free and $P_7$-freegraphs.In the last chapter of the manuscript, we disprove a conjecture of De Simoneand K"orner made in 1999 related to normal graphs. Our proof is probabilisticand is obtained by the use of random graphs
4
Lecat, Clément. "Réduction de l'espace de recherche du Problème de la Somme Coloration Minimum d'un graphe." Thesis, Amiens, 2017. http://www.theses.fr/2017AMIE0033/document.
Full textAbstract:
Le Problème de la Somme Coloration Minimum (MSCP) d'un graphe est un problème d'optimisation combinatoire dont l'objectif est de déterminer une coloration valide minimisant la somme des poids associés aux couleurs utilisées. Le nombre minimum de couleurs dans une solution optimale de MSCP est appelé la force du graphe, et la somme des poids des couleurs utilisées est appelée la somme chromatique du graphe. L'objectif de cette thèse a été d'étudier MSCP afin de proposer de nouvelles approches permettant sa résolution. La contribution de cette thèse est double. Premièrement, nous avons introduit deux nouvelles bornes supérieures de la force d'un graphe et une nouvelle borne inférieure de la somme chromatique, basées sur la notion de motif que nous avons adapté de la littérature. L'intérêt majeur de ces travaux est la réduction de l'espace des solutions de MSCP. Deuxièmement, nous avons proposé plusieurs approches de résolution exacte de MSCP. La première méthode consiste en une modélisation de MSCP en un formalisme MaxSAT partiel pondéré ou MinSAT partiel pondéré afin d'utiliser les solveurs MaxSAT/MinSAT de l'état de l'art pour résoudre MSCP. Nous avons montré que notre borne de la force du graphe permet de réduire grandement la taille des instances MaxSAT/MinSAT obtenues et de rendre les solveurs MaxSAT compétitifs pour résoudre MSCP. Les deux autres méthodes de résolution proposées sont des approches de type Branch-and-Bound appelées BBMSCP et 3LMSCP. La différence entre BBMSCP et 3LMSCP est que 3LMSCP exploite la partition du graphe en stables afin de ne pas considérer les colorations symétriquesThe Minimum Sum Coloring Problem (MSCP) of a graph is an optimization problem whose the aim is to find a valid coloring such that the sum of weights associated to the used color is minimum. The minimum number of colors needed in an optimal solution is called the strength of the graph, and the sum of weights of the colors used in an optimal solution is called the chromatic sum of the graph. The aim of this thesis was to study the MSCP in order to propose new approaches for its resolution. The contribution of the thesis is twofold. First, we have introduced two upper bounds of the strength and one lower bound of the chromatic sum of a graph, based on a notion called motif adapted from the literature. These bounds allow to reduce significantly the search space of the MSCP. Second, we have proposed several exact resolution methods for the MSCP. The first method consists in modelling the MSCP to a weighted partial MaxSAT or a weighted partial MinSAT and solves the MSCP using state-of-the-art MaxSAT/MinSAT solvers. We have showed that our upper bound of the strength allows to improve substantially the MaxSAT/MinSAT encodings, and consequently, the MaxSAT solvers are competitive to solve the MSCP. The two other resolution methods are based on the Branch-and-Bound scheme and are called BBMSCP and 3LMSCP respectively. The difference between BBMSCP and 3LMSCP is that BBMSCP explores many symmetric colorings but 3LMSCP exploits the partitions of the graph into stables to avoid symmetric colorings
5
Pierron, Théo. "Induction Schemes : From Language Separation to Graph Colorings." Thesis, Bordeaux, 2019. http://www.theses.fr/2019BORD0119/document.
Full textAbstract:
Cette thèse présente des résultats obtenus dans deux domaines : la théorie des langages, et la théorie des graphes. En théorie des langages, on s’intéresse à des problèmes de caractérisation de classes de langages réguliers. Le problème générique consiste à déterminer si un langage régulier donné peut être défini dans un certain formalisme. Les méthodes actuelles font intervenir un problème plus général appelé séparation. On présente ici deux types de contributions : une généralisation d’un résultat de décidabilité au cadre des langages de mots infinis, ainsi que des bornes inférieures pour la complexité du problème de séparation. En théorie des graphes, on considère le problème classique de coloration de graphes, où on cherche à attribuer des couleurs aux sommets d’un graphe de sorte que les sommets adjacents reçoivent des couleurs différentes, le but étant d’utiliser le moins de couleurs possible. Dans le cas des graphes peu denses, la méthode de déchargement est un atout majeur. Elle a notamment joué un rôle décisif dans la preuve du théorème des quatre couleurs. Cette méthode peut être vue comme une construction non conventionnelle d’un schéma de preuve par induction, spécifique à la classe de graphes et à la propriété considérées, et où la validité du schéma est rarement immédiate. On utilise des variantes de la méthode de déchargement pour étudier deux types de problèmes de colorationIn this thesis, we present results obtained in two fields: formal language theory and graph theory. In formal language theory, we consider some problems of characterization of classes of regular languages. The generic problem consists in determining whether a given regular language can be defined in a fixed formalism. The current approaches use a more general problem called separation. We present here two types of contributions: a generalization of a decidability result to the setting of infinite words, together with lower bounds for the complexity of the separation problem. In graph theory, we consider the classical problem of graph coloring, where we assign colors to vertices of a graph in such a way that two adjacent vertices receive different colors. The goal is to use the fewest colors. When the graphs are sparse, a crucial tool for this is the discharging method. It is most notably decisive in the proof of the Four-Color Theorem. This method can be seen as an unconventional construction of an inductive proof scheme, specific to the considered problem and graph class, where arguing the validity of the scheme is rarely immediate. We use variants of the discharging method to study two types of coloring problems
6
Gardi, Frédéric. "Ordonnancement avec exclusion mutuelle par un graphe d'intervalles ou d'une classe apparentée : complexité et algorithmes." Aix-Marseille 2, 2005. http://theses.univ-amu.fr.lama.univ-amu.fr/2005AIX22014.pdf.
Full text
7
Mortada, Maidoun. "The b-chromatic number of regular graphs." Thesis, Lyon 1, 2013. http://www.theses.fr/2013LYO10116.
Full textAbstract:
Les deux problèmes majeurs considérés dans cette thèse : le b-coloration problème et le graphe emballage problème. 1. Le b-coloration problème : Une coloration des sommets de G s'appelle une b-coloration si chaque classe de couleur contient au moins un sommet qui a un voisin dans toutes les autres classes de couleur. Le nombre b-chromatique b(G) de G est le plus grand entier k pour lequel G a une b-coloration avec k couleurs. EL Sahili et Kouider demandent s'il est vrai que chaque graphe d-régulier G avec le périmètre au moins 5 satisfait b(G) = d + 1. Blidia, Maffray et Zemir ont montré que la conjecture d'El Sahili et de Kouider est vraie pour d ≤ 6. En outre, la question a été résolue pour les graphes d-réguliers dans des conditions supplémentaires. Nous étudions la conjecture d'El Sahili et de Kouider en déterminant quand elle est possible et dans quelles conditions supplémentaires elle est vrai. Nous montrons que b(G) = d + 1 si G est un graphe d-régulier qui ne contient pas un cycle d'ordre 4 ni d'ordre 6. En outre, nous fournissons des conditions sur les sommets d'un graphe d-régulier G sans le cycle d'ordre 4 de sorte que b(G) = d + 1. Cabello et Jakovac ont prouvé si v(G) ≥ 2d3 - d2 + d, puis b(G) = d + 1, où G est un graphe d-régulier. Nous améliorons ce résultat en montrant que si v(G) ≥ 2d3 - 2d2 + 2d alors b(G) = d + 1 pour un graphe d-régulier G. 2. Emballage de graphe problème : Soit G un graphe d'ordre n. Considérer une permutation σ : V (G) → V (Kn), la fonction σ* : E(G) → E(Kn) telle que σ *(xy) = σ *(x) σ *(y) est la fonction induite par σ. Nous disons qu'il y a un emballage de k copies de G (dans le graphe complet Kn) s'il existe k permutations σi : V (G) → V (Kn), où i = 1, …, k, telles que σi*(E(G)) ∩ σj (E(G)) = ɸ pour i ≠ j. Un emballage de k copies d'un graphe G est appelé un k-placement de G. La puissance k d'un graphe G, noté par Gk, est un graphe avec le même ensemble de sommets que G et une arête entre deux sommets si et seulement si le distance entre ces deux sommets est au plus k. Kheddouci et al. ont prouvé que pour un arbre non-étoile T, il existe un 2-placement σ sur V (T). Nous introduisons pour la première fois le problème emballage marqué de graphe dans son graphe puissanceTwo problems are considered in this thesis: the b-coloring problem and the graph packing problem. 1. The b-Coloring Problem : A b-coloring of a graph G is a proper coloring of the vertices of G such that there exists a vertex in each color class joined to at least a vertex in each other color class. The b-chromatic number of a graph G, denoted by b(G), is the maximum number t such that G admits a b-coloring with t colors. El Sahili and Kouider asked whether it is true that every d-regular graph G with girth at least 5 satisfies b(G) = d + 1. Blidia, Maffray and Zemir proved that the conjecture is true for d ≤ 6. Also, the question was solved for d-regular graphs with supplementary conditions. We study El Sahili and Kouider conjecture by determining when it is possible and under what supplementary conditions it is true. We prove that b(G) = d+1 if G is a d-regular graph containing neither a cycle of order 4 nor of order 6. Then, we provide specific conditions on the vertices of a d-regular graph G with no cycle of order 4 so that b(G) = d + 1. Cabello and Jakovac proved that if v(G) ≥ 2d3 - d2 + d, then b(G) = d + 1, where G is a d-regular graph. We improve this bound by proving that if v(G) ≥ 2d3 - 2d2 + 2d, then b(G) = d+1 for a d-regular graph G. 2. Graph Packing Problem : Graph packing problem is a classical problem in graph theory and has been extensively studied since the early 70's. Consider a permutation σ : V (G) → V (Kn), the function σ* : E(G) → E(Kn) such that σ *(xy) = σ *(x) σ *(y) is the function induced by σ. We say that there is a packing of k copies of G into the complete graph Kn if there exist k permutations σ i : V (G) → V (Kn), where i = 1,…, k, such that σ*i (E(G)) ∩ σ*j (E(G)) = ɸ for I ≠ j. A packing of k copies of a graph G will be called a k-placement of G. The kth power Gk of a graph G is the supergraph of G formed by adding an edge between all pairs of vertices of G with distance at most k. Kheddouci et al. proved that for any non-star tree T there exists a 2-placement σ on V (T). We introduce a new variant of graph packing problem, called the labeled packing of a graph into its power graph
8
Chen, Min. "Vertex coloring of graphs via the discharging method." Thesis, Bordeaux 1, 2010. http://www.theses.fr/2010BOR14090/document.
Full textAbstract:
Dans cette thèse, nous nous intéressons à differentes colorations des sommets d’un graphe et aux homomorphismes de graphes. Nous nous intéressons plus spécialement aux graphes planaires et aux graphes peu denses. Nous considérons la coloration propre des sommets, la coloration acyclique, la coloration étoilée, lak-forêt-coloration, la coloration fractionnaire et la version par liste de la plupart de ces concepts.Dans le Chapitre 2, nous cherchons des conditions suffisantes de 3-liste colorabilité des graphes planaires. Ces conditions sont exprimées en termes de sous-graphes interdits et nos résultats impliquent plusieurs résultats connus.La notion de la coloration acyclique par liste des graphes planaires a été introduite par Borodin, Fon-Der Flaass, Kostochka, Raspaud, et Sopena. Ils ont conjecturé que tout graphe planaire est acycliquement 5-liste coloriable. Dans le Chapitre 3, on obtient des conditions suffisantes pour qu’un graphe planaire admette une k-coloration acyclique par liste avec k 2 f3; 4; 5g.Dans le Chapitre 4, nous montrons que tout graphe subcubique est 6-étoilé coloriable.D’autre part, Fertin, Raspaud et Reed ont montré que le graphe de Wagner ne peut pas être 5-étoilé-coloriable. Ce fait implique que notre résultat est optimal. De plus, nous obtenons des nouvelles bornes supérieures sur la choisissabilité étoilé d’un graphe planaire subcubique de maille donnée.Une k-forêt-coloration d’un graphe G est une application ¼ de l’ensemble des sommets V (G) de G dans l’ensemble de couleurs 1; 2; ¢ ¢ ¢ ; k telle que chaque classede couleur induit une forêt. Le sommet-arboricité de G est le plus petit entier ktel que G a k-forêt-coloration. Dans le Chapitre 5, nous prouvons une conjecture de Raspaud et Wang affirmant que tout graphe planaire sans triangles intersectants admet une sommet-arboricité au plus 2.Enfin, au Chapitre 6, nous nous concentrons sur le problème d’homomorphisme des graphes peu denses dans le graphe de Petersen. Plus précisément, nous prouvons que tout graphe sans triangles ayant un degré moyen maximum moins de 5=2 admet un homomorphisme dans le graphe de Petersen. En outre, nous montrons que la borne sur le degré moyen maximum est la meilleure possibleIn this thesis, we are interested in various vertex coloring and homomorphism problems of graphs with special emphasis on planar graphs and sparsegraphs. We consider proper vertex coloring, acyclic coloring, star coloring, forestcoloring, fractional coloring and the list version of most of these concepts.In Chapter 2, we consider the problem of finding sufficient conditions for a planargraph to be 3-choosable. These conditions are expressed in terms of forbiddensubgraphs and our results extend several known results.The notion of acyclic list coloring of planar graphs was introduced by Borodin,Fon-Der Flaass, Kostochka, Raspaud, and Sopena. They conjectured that everyplanar graph is acyclically 5-choosable. In Chapter 3, we obtain some sufficientconditions for planar graphs to be acyclically k-choosable with k 2 f3; 4; 5g.In Chapter 4, we prove that every subcubic graph is 6-star-colorable. On theother hand, Fertin, Raspaud and Reed showed that the Wagner graph cannot be5-star-colorable. This fact implies that our result is best possible. Moreover, weobtain new upper bounds on star choosability of planar subcubic graphs with givengirth.A k-forest-coloring of a graph G is a mapping ¼ from V (G) to the set f1; ¢ ¢ ¢ ; kgsuch that each color class induces a forest. The vertex-arboricity of G is the smallestinteger k such that G has a k-forest-coloring. In Chapter 5, we prove a conjecture ofRaspaud and Wang asserting that every planar graph without intersecting triangleshas vertex-arboricity at most 2.Finally, in Chapter 6, we focus on the homomorphism problems of sparse graphsto the Petersen graph. More precisely, we prove that every triangle-free graph withmaximum average degree less than 5=2 admits a homomorphism to the Petersengraph. Moreover, we show that the bound on the maximum average degree in ourresult is best possible
9
Weinberg, Benjamin Talbi El-Ghazali. "Analyse et résolution approchée de problèmes d'optimisation combinatoire application au problème de coloration de graphe /." Villeneuve d'Ascq : Université des sciences et technologies de Lille, 2007. https://iris.univ-lille1.fr/dspace/handle/1908/973.
Full textAbstract:
Reproduction de : Thèse de doctorat : Informatique : Lille 1 : 2004.N° d'ordre (Lille 1) : 3467. Résumé en français et en anglais. Titre provenant de la page de titre du document numérisé. Bibliogr. 9 p.
10
Weinberg, Benjamin. "Analyse et résolution approchée de problèmes d'optimisation combinatoire : application au problème de coloration de graphe." Lille 1, 2004. https://pepite-depot.univ-lille.fr/LIBRE/Th_Num/2004/50376-2004-Weinberg.pdf.
Full textAbstract:
Nous avons exploré plusieurs aspects théoriques et expérimentaux de l'optimisation combinatoire. Premièrement, nous avons défini une notion de structure permettant de s'échapper du résultat du théorème du No Free Lunch. Deuxièmement nous avons formalisé la symétrie de l'espace de recherche des problèmes de partitionnements. A l'aide de cette formalisation, nous pûmes concevoir des outils travaillant efficacement sur cette espace. Plus précisément nous avons développé un test d'égalité, une mesure de distance et un nouvel opérateur de Cross over. Nous avons utilisé ces résultats pour classifier les benchmarks classique de la coloration de graphe. Pour finir, nous avons développe pour ce problème une métaheuristique parallèle qui équilibre l'intensification et la diversification pendant la recherche.
Books on the topic "Coloriage de graphe"
1
Kubale, Marek, ed. Graph Colorings. Providence, Rhode Island: American Mathematical Society, 2004. http://dx.doi.org/10.1090/conm/352.
Full text
4
Jensen, Tommy R., and Bjarne Toft. Graph Coloring Problems. Hoboken, NJ, USA: John Wiley & Sons, Inc., 1994. http://dx.doi.org/10.1002/9781118032497.
Full text
6
Zhang, Ping. Color-Induced Graph Colorings. Cham: Springer International Publishing, 2015. http://dx.doi.org/10.1007/978-3-319-20394-2.
Full text
8
Salavatipour, Mohammadreza. On sum coloring of graphs. Toronto: University of Toronto, Dept. of Computer Science, 2000.
Find full text
9
Zhang, Ping. A Kaleidoscopic View of Graph Colorings. Cham: Springer International Publishing, 2016. http://dx.doi.org/10.1007/978-3-319-30518-9.
Full text
10
1949-, Rödl Vojtěch, Ruciński Andrzej, and Tetali Prasad, eds. A Sharp threshold for random graphs with a monochromatic triangle in every edge coloring. Providence, R.I: American Mathematical Society, 2006.
Find full textBook chapters on the topic "Coloriage de graphe"
1
Jungnickel, Dieter. "Colorings." In Graphs, Networks and Algorithms, 275–93. Berlin, Heidelberg: Springer Berlin Heidelberg, 2013. http://dx.doi.org/10.1007/978-3-642-32278-5_9.
Full text
2
Fisk, Steve. "Chapter 4: Graphs." In Coloring Theories, 63–84. Providence, Rhode Island: American Mathematical Society, 1989. http://dx.doi.org/10.1090/conm/103/04.
Full text
3
Saoub, Karin R. "Graph Coloring." In Graph Theory, 275–338. Boca Raton: CRC Press, 2021. | Series: Textbooks in mathematics: Chapman and Hall/CRC, 2021. http://dx.doi.org/10.1201/9781138361416-6.
Full text
4
Wallis, W. D. "Graph Colorings." In A Beginner’s Guide to Graph Theory, 93–111. Boston, MA: Birkhäuser Boston, 2007. http://dx.doi.org/10.1007/978-0-8176-4580-9_7.
Full text
5
Balakrishnan, R., and K. Ranganathan. "Graph Colorings." In A Textbook of Graph Theory, 143–74. New York, NY: Springer New York, 2012. http://dx.doi.org/10.1007/978-1-4614-4529-6_7.
Full text
6
Melnikov, O., V. Sarvanov, R. Tyshkevich, V. Yemelichev, and I. Zverovich. "Graph Colorings." In Kluwer Texts in the Mathematical Sciences, 135–50. Dordrecht: Springer Netherlands, 1998. http://dx.doi.org/10.1007/978-94-017-1514-0_10.
Full text
7
Balakrishnan, R., and K. Ranganathan. "Graph Colorings." In A Textbook of Graph Theory, 128–51. New York, NY: Springer New York, 2000. http://dx.doi.org/10.1007/978-1-4419-8505-7_7.
Full text
8
Wallis, W. D. "Graph Colorings." In A Beginner’s Guide to Graph Theory, 85–104. Boston, MA: Birkhäuser Boston, 2000. http://dx.doi.org/10.1007/978-1-4757-3134-7_7.
Full text
9
Dorne, Raphaël, and Jin-Kao Hao. "Tabu Search for Graph Coloring, T-Colorings and Set T-Colorings." In Meta-Heuristics: Advances and Trends in Local Search Paradigms for Optimization, 77–92. Boston, MA: Springer US, 1999. http://dx.doi.org/10.1007/978-1-4615-5775-3_6.
Full text
10
Langberg, Michael. "Graph Coloring." In Encyclopedia of Algorithms, 368–71. Boston, MA: Springer US, 2008. http://dx.doi.org/10.1007/978-0-387-30162-4_170.
Full textConference papers on the topic "Coloriage de graphe"
1
Hebrard, Emmanuel, and George Katsirelos. "Clause Learning and New Bounds for Graph Coloring." In Twenty-Eighth International Joint Conference on Artificial Intelligence {IJCAI-19}. California: International Joint Conferences on Artificial Intelligence Organization, 2019. http://dx.doi.org/10.24963/ijcai.2019/856.
Full textAbstract:
Graph coloring is a major component of numerous allocation and scheduling problems. We introduce a hybrid CP/SAT approach to graph coloring based on exploring Zykov’s tree: for two non-neighbors, either they take a different color and there might as well be an edge between them, or they take the same color and we might as well merge them. Branching on whether two neighbors get the same color yields a symmetry-free tree with complete graphs as leaves, which correspond to colorings of the original graph. We introduce a new lower bound for this problem based on Mycielskian graphs; a method to produce a clausal explanation of this bound for use in a CDCL algorithm; and a branching heuristic emulating Brelaz on the Zykov tree. The combination of these techniques in a branch- and-bound search outperforms Dsatur and other SAT-based approaches on standard benchmarks both for finding upper bounds and for proving lower bounds.
2
Andrade, Davi de, and Ana Silva. "On the Complexity of Subfall Coloring of Graphs." In Encontro de Teoria da Computação. Sociedade Brasileira de Computação - SBC, 2021. http://dx.doi.org/10.5753/etc.2021.16383.
Full textAbstract:
Given a graph G and a proper k-coloring f of G, a b-vertex in f is a vertex that is adjacent to every color class but its own. If every vertex is a b-vertex, then f is a fall k-coloring; and G has a subfall k-coloring if there is an induced H $\subseteq$ G such that H has a fall k-coloring. The subfall chromatic number of G is the largest positive integer $\psi_{fs}(G)$ such that G has a subfall $\psi_{fs}(G)$-coloring. We prove that deciding if a graph G has a subfall k-coloring is NP-complete for k $\geq$ 4, and characterize graphs having a subfall 3-coloring. This answers a question posed by Dunbar et al. (2000) in their seminal paper. We also prove polinomiality for chordal graphs and cographs, and present a comparison with other known coloring metrics based on heuristics.
3
Lin, Jinkun, Shaowei Cai, Chuan Luo, and Kaile Su. "A Reduction based Method for Coloring Very Large Graphs." In Twenty-Sixth International Joint Conference on Artificial Intelligence. California: International Joint Conferences on Artificial Intelligence Organization, 2017. http://dx.doi.org/10.24963/ijcai.2017/73.
Full textAbstract:
The graph coloring problem (GCP) is one of the most studied NP hard problems and has numerous applications. Despite the practical importance of GCP, there are limited works in solving GCP for very large graphs. This paper explores techniques for solving GCP on very large real world graphs.We first propose a reduction rule for GCP, which is based on a novel concept called degree bounded independent set.The rule is iteratively executed by interleaving between lower bound computation and graph reduction. Based on this rule, we develop a novel method called FastColor, which also exploits fast clique and coloring heuristics. We carry out experiments to compare our method FastColor with two best algorithms for coloring large graphs we could find. Experiments on a broad range of real world large graphs show the superiority of our method. Additionally, our method maintains both upper bound and lower bound on the optimal solution, and thus it proves an optimal solution when the upper bound meets the lower bound. In our experiments, it proves the optimal solution for 97 out of 142 instances.
4
Domingues, Kenny, Yuri Silva de Oliveira, and Ana Silva. "Lower Bounds for the Partial Grundy Number of the Lexicographic Product of Graphs." In Encontro de Teoria da Computação. Sociedade Brasileira de Computação - SBC, 2021. http://dx.doi.org/10.5753/etc.2021.16376.
Full textAbstract:
A Grundy coloring of a graph $G$ is a coloring obtained by applying the greedy algorithm according to some order of the vertices of $G$. The Grundy number of $G$ is then the largest $k$ such that $G$ has a greedy coloring with $k$ colors. A partial Grundy coloring is a coloring where each color class contains at least one greedily colored vertex, and the partial Grundy number of $G$ is the largest $k$ for which $G$ has a partial greedy coloring. In this article, we give some results on the partial Grundy number of the lexicographic product of graphs, drawing a parallel with known results for the Grundy number.
5
Sobral, Gabriel A. G., Marina Groshaus, and André L. P. Guedes. "Biclique edge-choosability in some classes of graphs∗." In II Encontro de Teoria da Computação. Sociedade Brasileira de Computação - SBC, 2017. http://dx.doi.org/10.5753/etc.2017.3203.
Full textAbstract:
In this paper we study the problem of coloring the edges of a graph for any k-list assignment such that there is no maximal monochromatic biclique, in other words, the k-biclique edge-choosability problem. We prove that the K3free graphs that are not odd cycles are 2-star edge-choosable, chordal bipartite graphs are 2-biclique edge-choosable and we present a lower bound for the biclique choice index of power of cycles and power of paths. We also provide polynomial algorithms to compute a 2-biclique (star) edge-coloring for K3-free and chordal bipartite graphs for any given 2-list assignment to edges.
6
Rocha, Aleffer, Sheila M. Almeida, and Leandro M. Zatesko. "The Rainbow Connection Number of Triangular Snake Graphs." In Encontro de Teoria da Computação. Sociedade Brasileira de Computação - SBC, 2020. http://dx.doi.org/10.5753/etc.2020.11091.
Full textAbstract:
Rainbow coloring problems, of noteworthy applications in Information Security, have been receiving much attention last years in Combinatorics. The rainbow connection number of a graph G is the least number of colors for a (not necessarily proper) edge coloring of G such that between any pair of vertices there is a path whose edge colors are all distinct. In this paper we determine the rainbow connection number of the triple triangular snake graphs.
7
Jothilakshmi, G., U. Mary, and S. Monolisa. "On bDS - Coloring of corona graph of certain graphs." In PROCEEDINGS OF INTERNATIONAL CONFERENCE ON ADVANCES IN MATERIALS RESEARCH (ICAMR - 2019). AIP Publishing, 2020. http://dx.doi.org/10.1063/5.0016837.
Full text
8
Dasoulas, George, Ludovic Dos Santos, Kevin Scaman, and Aladin Virmaux. "Coloring Graph Neural Networks for Node Disambiguation." In Twenty-Ninth International Joint Conference on Artificial Intelligence and Seventeenth Pacific Rim International Conference on Artificial Intelligence {IJCAI-PRICAI-20}. California: International Joint Conferences on Artificial Intelligence Organization, 2020. http://dx.doi.org/10.24963/ijcai.2020/294.
Full textAbstract:
In this paper, we show that a simple coloring scheme can improve, both theoretically and empirically, the expressive power of Message Passing Neural Networks (MPNNs). More specifically, we introduce a graph neural network called Colored Local Iterative Procedure (CLIP) that uses colors to disambiguate identical node attributes, and show that this representation is a universal approximator of continuous functions on graphs with node attributes. Our method relies on separability, a key topological characteristic that allows to extend well-chosen neural networks into universal representations. Finally, we show experimentally that CLIP is capable of capturing structural characteristics that traditional MPNNs fail to distinguish, while being state-of-the-art on benchmark graph classification datasets.
9
Atici, Mustafa. "Graph coloring." In the 49th Annual Southeast Regional Conference. New York, New York, USA: ACM Press, 2011. http://dx.doi.org/10.1145/2016039.2016082.
Full text
10
Streicher, Simon, and Johan du Preez. "Graph Coloring." In the ACM Multimedia 2017 Workshop. New York, New York, USA: ACM Press, 2017. http://dx.doi.org/10.1145/3132711.3132717.
Full textReports on the topic "Coloriage de graphe"
1
Rodger, C. A., D. G. Hoffman, P. D. Johnson, and Jr. Connectivity and Colorings of Graphs. Fort Belvoir, VA: Defense Technical Information Center, March 2002. http://dx.doi.org/10.21236/ada400177.
Full text
2
Rosenfeld, A. ARC Colorings, Partial Path Groups, and Parallel Graph Contractions. Fort Belvoir, VA: Defense Technical Information Center, July 1985. http://dx.doi.org/10.21236/ada158918.
Full text
3
Jones, M. T., and P. E. Plassmann. Parallel iterative solution of sparse linear systems using orderings from graph coloring heuristics. Office of Scientific and Technical Information (OSTI), December 1990. http://dx.doi.org/10.2172/10148824.
Full text
4
Wan, Wei. A New Approach to the Decomposition of Incompletely Specified Functions Based on Graph Coloring and Local Transformation and Its Application to FPGA Mapping. Portland State University Library, January 2000. http://dx.doi.org/10.15760/etd.6582.
Full text