Relevant bibliographies by topics / Graph coloring

Contents

  1. Journal articles
  2. Dissertations / Theses
  3. Books
  4. Book chapters
  5. Conference papers
  6. Reports

Academic literature on the topic 'Graph coloring'

Author: Grafiati
Published: 4 June 2021
Last updated: 25 May 2024

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles

Select a source type:

Consult the lists of relevant articles, books, theses, conference reports, and other scholarly sources on the topic 'Graph coloring.'

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 "Graph coloring"

1

Prajnanaswaroopa, Shantharam, Jayabalan Geetha, Kanagasabapathi Somasundaram, and Teerapong Suksumran. "Total Coloring of Some Classes of Cayley Graphs on Non-Abelian Groups." Symmetry 14, no. 10 (October 17, 2022): 2173. http://dx.doi.org/10.3390/sym14102173.

Full text
Abstract:
Total Coloring of a graph G is a type of graph coloring in which any two adjacent vertices, an edge, and its incident vertices or any two adjacent edges do not receive the same color. The minimum number of colors required for the total coloring of a graph is called the total chromatic number of the graph, denoted by χ″(G). Mehdi Behzad and Vadim Vizing simultaneously worked on the total colorings and proposed the Total Coloring Conjecture (TCC). The conjecture states that the maximum number of colors required in a total coloring is Δ(G)+2, where Δ(G) is the maximum degree of the graph G. Graphs derived from the symmetric groups are robust graph structures used in interconnection networks and distributed computing. The TCC is still open for the circulant graphs. In this paper, we derive the upper bounds for χ″(G) of some classes of Cayley graphs on non-abelian groups, typically Cayley graphs on the symmetric groups and dihedral groups. We also obtain the upper bounds of the total chromatic number of complements of Kneser graphs.
APA, Harvard, Vancouver, ISO, and other styles
2

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 text
Abstract:
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.
APA, Harvard, Vancouver, ISO, and other styles
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 text
Abstract:
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.
APA, Harvard, Vancouver, ISO, and other styles
4

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 text
Abstract:
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.
APA, Harvard, Vancouver, ISO, and other styles
5

Nuroeni, Ilmiatun, Arika Indah Kristiana, Saddam Hussen, Susi Setiawani, and Robiatul Adawiyah. "LOCAL IRREGULARITY POINT COLORING ON THE RESULT OF SUBDIVISION OPERATION OF HELM GRAPHS." Jurnal Diferensial 5, no. 2 (October 20, 2023): 117–25. http://dx.doi.org/10.35508/jd.v5i2.12197.

Full text
Abstract:
One of the sub-chapters studied in graphs is local irregularity vertex coloring of graph. The based on definition of local irregularity vertex coloring of graph, as follow : (i)l : V (G) →{1, 2, 3, . . . , k} as a vertex irregular labeling and w : V (G) → N, for every uv ∈ E(G), w(u) ̸=w(v) with w(u) = Pv∈N(u)l(v) and (i) Opt(l) = min{max(li); li is a vertex irregular labeling}. The chromatic number of the local irregularity vertex coloring of G denoted by χlis(G), is the minimum cardinality of the largest label over all such local irregularity vertex colorings. In this article, discuss about local irregularity vertex coloring of subdivision by helm graph (Sg(Hn)).
APA, Harvard, Vancouver, ISO, and other styles
6

Ma, Baolin, and Chao Yang. "Distinguishing colorings of graphs and their subgraphs." AIMS Mathematics 8, no. 11 (2023): 26561–73. http://dx.doi.org/10.3934/math.20231357.

Full text
Abstract:
<abstract><p>In this paper, several distinguishing colorings of graphs are studied, such as vertex distinguishing proper edge coloring, adjacent vertex distinguishing proper edge coloring, vertex distinguishing proper total coloring, adjacent vertex distinguishing proper total coloring. Finally, some related chromatic numbers are determined, especially the comparison of the correlation chromatic numbers between the original graph and the subgraphs are obtained.</p></abstract>
APA, Harvard, Vancouver, ISO, and other styles
7

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 text
Abstract:
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.
APA, Harvard, Vancouver, ISO, and other styles
8

Li, Minhui, Shumin Zhang, Caiyun Wang, and Chengfu Ye. "The Dominator Edge Coloring of Graphs." Mathematical Problems in Engineering 2021 (October 7, 2021): 1–7. http://dx.doi.org/10.1155/2021/8178992.

Full text
Abstract:
Let G be a simple graph. A dominator edge coloring (DE-coloring) of G is a proper edge coloring in which each edge of G is adjacent to every edge of some color class (possibly its own class). The dominator edge chromatic number (DEC-number) of G is the minimum number of color classes among all dominator edge colorings of G , denoted by χ d ′ G . In this paper, we establish the bounds of the DEC-number of a graph, present the DEC-number of special graphs, and study the relationship of the DEC-number between G and the operations of G .
APA, Harvard, Vancouver, ISO, and other styles
9

A. Prasanna, M. A. Rifayathali, and S. Ismail Mohideen. "Hesitancy Fuzzy Graph Coloring." International Journal of Fuzzy Mathematical Archive 14, no. 02 (2017): 179–89. http://dx.doi.org/10.22457/ijfma.v14n2a2.

Full text
Abstract:
Graph coloring dates back to 1852, when Francis Guthrie come up with the four color conjecture. Gary Chartrand and Ping Zhang [3] discussed various colorings of graph and its properties in their book entitled Chromatic Graph Theory. A graph coloring is the assignment of a color to each of the vertices or edges or both in such a way that no two adjacent vertices and incident edges share the same color. Graph coloring has been applied to many real world problems like scheduling, allocation, telecommunications and bioinformatics, etc.
APA, Harvard, Vancouver, ISO, and other styles
10

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 text
Abstract:
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.
APA, Harvard, Vancouver, ISO, and other styles
More sources

Dissertations / Theses on the topic "Graph coloring"

1

Sun, Pak Kiu. "Incidence coloring : origins, developments and relation with other colorings." HKBU Institutional Repository, 2007. http://repository.hkbu.edu.hk/etd_ra/826.

Full text
APA, Harvard, Vancouver, ISO, and other styles
2

Araujo, Julio. "Graph coloring and graph convexity." Nice, 2012. http://www.theses.fr/2012NICE4032.

Full text
Abstract:
Dans cette thèse, nous étudions plusieurs problèmes de théorie des graphes concernant la coloration et la convexité des graphes. La plupart des résultats figurant ici sont liés à la complexité de calcul de ces problèmes pour certaines classes de graphes. Dans la première, et principale, partie de cette thèse, nous traitons la coloration des graphes qui est l’un des domaines les plus étudiés de théorie des graphes. Nous considérons d’abord trois problèmes de coloration appelés coloration gloutonne, coloration pondérée et coloration pondérée impropre. Ensuite, nous traitons un problème de décision, appelé bon étiquetage d’arêtes, dont la définition a été motivée par le problème d’affectation de longueurs d’onde dans les réseaux optiques. La deuxième partie de cette thèse est consacrée à un paramètre d’optimisation des graphes appelé le nombre enveloppe (géodésique). La définition de ce paramètre est motivée par une extension aux graphes des notions d’ensembles et d’enveloppes convexes dans l’espace Euclidien. Enfin, nous présentons dans l’annexe d’autres travaux développés au cours de cette thèse, l’un sur les hypergraphes orientés Eulériens et Hamiltoniens et l’autre concernant les systèmes de stockage distribués
In this thesis, we study several problems of Graph Theory concerning Graph Coloring and Graph Convexity. Most of the results contained here are related to the computational complexity of these problems for particular graph classes. In the first and main part of this thesis, we deal with Graph Coloring which is one of the most studied areas of Graph Theory. We first consider three graph coloring problems called Greedy Coloring, Weighted Coloring and Weighted Improper Coloring. Then, we deal with a decision problem, called Good Edge-Labelling, whose definition was motivated by the Wavelength Assignment problem in optical networks. The second part of this thesis is devoted to a graph optimization parameter called (geodetic) hull number. The definition of this parameter is motivated by an extension to graphs of the notions of convex sets and convex hulls in the Euclidean space. Finally, we present in the appendix other works developed during this thesis, one about Eulerian and Hamiltonian directed hypergraphs and the other concerning distributed storage systems
APA, Harvard, Vancouver, ISO, and other styles
3

Normann, Per. "Parallel graph coloring : Parallel graph coloring on multi-core CPUs." Thesis, Uppsala universitet, Avdelningen för beräkningsvetenskap, 2014. http://urn.kb.se/resolve?urn=urn:nbn:se:uu:diva-227656.

Full text
Abstract:
In recent times an evident trend in hardware is to opt for multi-core CPUs. This has lead to a situation where an increasing number of sequential algorithms are parallelized to fit these new multi-core environments. The greedy Multi-Coloring algorithm is a strictly sequential algorithm that is used in a wide range of applications. The application in focus is on decomposition by graph coloring for preconditioning techniques suitable for iterative solvers like the and methods. In order to perform all phases of these iterative solvers in parallel the graph analysis phase needs to be parallelized. Albeit many attempts have been made to parallelize graph coloring non of these attempts have successfully put the greedy Multi-Coloring algorithm into obsolescence. In this work techniques for parallel graph coloring are proposed and studied. Quantitative results, which represent the number of colors, confirm that the best new algorithm, the Normann algorithm, is performing on the same level as the greedy Multi-Coloring algorithm. Furthermore, in multi-core environments the parallel Normann algorithm fully outperforms the classical greedy Multi-Coloring algorithm for all large test matrices. With the features of the Normann algorithm quantified and presented in this work it is now possible to perform all phases of iterative solvers like and methods in parallel.
APA, Harvard, Vancouver, ISO, and other styles
4

Labelle, François. "Graph embeddings and approximate graph coloring." Thesis, National Library of Canada = Bibliothèque nationale du Canada, 2000. http://www.collectionscanada.ca/obj/s4/f2/dsk1/tape3/PQDD_0031/MQ64386.pdf.

Full text
APA, Harvard, Vancouver, ISO, and other styles
5

Le, Ngoc Khang. "Detecting and Coloring some Graph Classes." Thesis, Lyon, 2018. http://www.theses.fr/2018LYSEN021/document.

Full text
Abstract:
Les graphes sont des structures mathématiques utilisées pour modéliser les relations par paires entre objets. Malgré leur structure simple, les graphes ont des applications dans divers domaines tels que l'informatique, la physique, la biologie et la sociologie. L'objectif principal de ce travail est de continuer l'étude des problèmes de coloration et de détection dans le cadre de classes de graphes fermées par sous-graphes induits (que nous appelons classes de graphes héréditaires).La première classe que nous considérons est graphes sans ISK4 - les graphes qui ne contiennent aucune subdivision de en tant que sous-graphe induit. Nous montrons que le nombre chromatique de cette classe est limité à 24, une amélioration considérable par rapport à la borne existant précédemment. Nous donnons également une bien meilleure limite dans le cas sans triangle. De plus, nous prouvons qu'il existe un algorithme de complexité pour détecter cette classe, ce qui répond à une question de Chudnovsky et al. et Lévêque et al.La deuxième classe que nous étudions est celle des graphes sans trou pair et sans étoile d’articulation. Cela est motivé par l'utilisation de la technique de décomposition pour résoudre certains problèmes d'optimisation. Nous garantissons la fonction χ-bounding optimale pour cette classe. Nous montrons que la classe a rank-width bornée, ce qui implique l'existence d'un algorithme de coloration en temps polynomial. Enfin, la coloration gloutonne connexe dans les graphes sans griffes est considérée. Une façon naturelle de colorier un graphe est d'avoir un ordre de ses sommets et d'affecter pour chaque sommet la première couleur disponible. Beaucoup de recherches ont été faites pour des ordres généraux. Cependant, nous connaissons très peu de choses sur la caractérisation des bons graphes par rapport aux ordres connexes. Un graphe est bon si pour chaque sous-graphe induit connexe de , chaque ordre connexe donne à une coloration optimale. Nous donnons la caractérisation complète de bons graphes sans griffes en termes de sous-graphes induits minimaux interdits
Graphs are mathematical structures used to model pairwise relations between objects. Despite their simple structures, graphs have applications in various areas like computer science, physics, biology and sociology. The main focus of this work is to continue the study of the coloring and detecting problems in the setting of graph classes closed under taking induced subgraphs (which we call hereditary graph classes). The first class we consider is ISK4-free graphs - the graphs that do not contain any subdivision of K4 as an induced subgraph. We prove that the chromatic number of this class is bounded by 24, a huge improvement compared to the best-known bound. We also give a much better bound in the triangle-free case. Furthermore, we prove that there exists an O(n 9) algorithm for detecting this class, which answers a question by Chudnovsky et al. and Lévêque et al. The second class we study is even-hole-free graphs with no star cutset. This was motivated by the use of decomposition technique in solving some optimization problems. We prove the optimal χ -bounding function for this class and show that it has bounded rank-width, which implies the existence of a polynomial-time coloring algorithm.Finally, the connected greedy coloring in claw-free graphs is considered. A natural way to color a graph is to have an order of its vertices and assign for each vertex the first available color. A lot of researches have been done for general orders. However, we know very little about the characterization of good graphs with respect to connected orders. A graph G is good if for every connected induced subgraph H of G, every connected order gives H an optimal coloring. We give the complete characterization of good claw-free graphs in terms of minimal forbidden induced subgraphs
APA, Harvard, Vancouver, ISO, and other styles
6

Casselgren, Carl Johan. "On some graph coloring problems." Doctoral thesis, Umeå universitet, Institutionen för matematik och matematisk statistik, 2011. http://urn.kb.se/resolve?urn=urn:nbn:se:umu:diva-43389.

Full text
APA, Harvard, Vancouver, ISO, and other styles
7

Bacak, Gökşen Ufuktepe Ünal. "Vertex Coloring of A Graph/." [s.l.] : [s.n.], 2004. http://library.iyte.edu.tr/tezler/master/matematik/T000416.pdf.

Full text
APA, Harvard, Vancouver, ISO, and other styles
8

Beşeri, Tina Ufuktepe Ünal. "Edge Coloring of A Graph/." [s.l.]: [s.n.], 2004. http://library.iyte.edu.tr/tezler/master/matematik/T000439.pdf.

Full text
APA, Harvard, Vancouver, ISO, and other styles
9

Jiang, Yiting. "Many aspects of graph coloring." Electronic Thesis or Diss., Université Paris Cité, 2022. https://wo.app.u-paris.fr/cgi-bin/WebObjects/TheseWeb.woa/wa/show?t=5613&f=42533.

Full text
Abstract:
La coloration des graphes est un sujet central en théorie des graphes, et divers concepts de coloration ont été étudiés dans la littérature. Cette thèse étudie certains de ces concepts de coloration et les problèmes associés. Il s'agit notamment de la coloration des graphes signés généralisés, du nombre de choix fractionnels forts des graphes, du nombre de coloration généralisé des graphes, de la largeur gémellaire des graphes, de la discordance (combinatoire) des systèmes d'ensembles définissables et des classes de graphes chi_p-bornées. Un graphe signé est une paire (G, sigma), où G est un graphe et sigma: E(G) to {+,-} est une signature. Un graphe signé généralisé est également une paire (G, sigma), où la signature sigma attribue à chaque arête e une permutation sigma(e) dans un ensemble S comme son signe. Dans une coloration d'un graphe signé ou d'un graphe signé généralisé (G, sigma), le signe sigma(e) détermine les paires de couleurs qui doivent être évitées en tant que couleurs des sommets terminaux de e. Une question naturelle motivée par le théorème des quatre couleurs est de savoir pour quels sous-ensembles S de S_4, tout graphe planaire est S-4-colorable. Cette question a maintenant une réponse complète: seul S={id} posséde cette propriété, ce qui signifie que le théorème des quatre couleurs est strict au sens de la coloration généralisée des graphes signés. Ce résulat a été établi par une séquence de six articles, par différents groupes d'auteurs. L'une des contributions de cette thése est le résultat établi dans l'un de ces articles, à savoir que que de nombreux ensembles S n'ont pas la propriété désirée. La thèse considère également des questions similaires pour les graphes planaires sans triangle, ce qui peut être considéré comme une exploration de l'étanchéité du théorème de Grötzsch. Notre résultat montre que pour tout sous-ensemble S de S_3, si S n'est pas conjugué à un sous-ensemble de {id, (12)}, alors il existe un graphe planaire sans triangle qui n'est pas S-3-colorable. Une autre tentative pour renforcer le théorème de Grötzsch est de considérer le nombre de choix fractionnaire fort des graphes planaires sans triangle. Il a été prouvé par Voigt qu'il existe des graphes planaires sans triangle qui ne sont pas 3-choissables. Cette thèse prouve que le supremum du nombre de choix fractionnel fort des graphes planaires sans triangle est au moins 3+1/17. Un sujet important de la théorie structurelle des graphes est l'étude de la complexité structurelle des graphes. Quelques concepts et invariants de graphes sont largement étudiés dans la littérature. Récemment, le concept de largeur gémellaire a été introduit. Dans cette thèse, nous prouvons qu'un graphe G sans sous graphe K_{s,s} et de largeur gémellaire d a ses nombres de coloration forts (faibles) r bornés supérieurement par une fonction exponentielle en r et que nous pouvons construire des graphes réalisant une telle dépendance en r. L'une des deux notions centrales de la théorie structurelle des classes de graphes éparses est celle de classes d'expansion bornée. La discordance combinatoire est un sujet important. Elle mesure les irrégularités inévitables des systèmes d'ensembles et la difficulté intrinsèque de leur approximation. Dans cette thèse, nous donnons une nouvelle caractérisation des classes d'expansion bornée en termes de discordance de système définissables. La notion de chi-boundedness est un sujet central en théorie des graphes chromatiques. Dans cette thèse, les classes chi-bornées sont étudiées ici dans le contexte des colorations stellaires et, plus généralement, des chi_p-colorations. Considéré dans le cadre général de l'édute des classes éparses, il conduit à des extensions naturelles de la notion de classe d'expansion bornée. Nous résolvons ici deux conjectures liées à la limitation du nombre chromatique stellaire (i.e. chi_2). Nous donnons des caractérisations structurelles des classes (fortement et faiblement) chi_p-bornée
Graph coloring is a central topic in graph theory, and various coloring concepts have been studied in the literature. This thesis studies some of the coloring concepts and related problems. These include coloring of generalized signed graphs, strong fractional choice number of graphs, generalized coloring number of graphs, twin-width of graphs, (combinatorial) discrepancy of definable set systems and chi_p-bounded classes of graphs. A signed graph is a pair (G, sigma), where G is a graph and sigma: E(G) to {+,-} is a signature. A generalized signed graph is also a pair (G, sigma), where the signature sigma assigns to each edge e a permutation sigma(e) in a set S as its sign. In a coloring of a signed graph or a generalized signed graph (G, sigma), the sign sigma(e) determines the pairs of colors that need to be avoided as the colors of the end vertices of e. Let S_k be the set of all permutations of [k]. A natural question motivated by the four color theorem is for which subsets S of S_4, every planar graph is S-4-colorable. This question is now completely answered: only S={id} has this property, which means that the four color theorem is tight in the sense of generalized signed graph coloring. This answer is obtained in a sequence of six papers, by different groups of authors. The contribution of this thesis is the results in one of the papers, which shows that many sets S do not have the desired property. The thesis also considers similar questions for triangle-free planar graphs, which can be viewed as exploring the tightness of Grötzsch Theorem. Our result shows that for any subset S of S_3, if S is not conjugate to a subset of {id, (12)}, then there exists a triangle-free planar graph which is not S-3-colorable. Another attempt to strengthen Grötzsch Theorem is to consider multiple list coloring of triangle-free planar graphs. It was proved by Voigt that there are triangle-free planar graphs that are not 3-choosable. This thesis strengthens Voigt's result by considering the strong fractional choice number of graphs and proves that the supremum of the strong fractional choice number of triangle-free planar graphs is at least 3+1/17. One important subject in structural graph theory is to study the structural complexity of graphs or classes of graphs and a few concepts and graph invariants are studied extensively in the literature. These include treewidth of graphs, generalized coloring number, etc. Recently, the concept of twin-width was introduced by Bonnet, Kim, Thomassé and Watrigant. In this thesis, we study the relation between twin-width and generalized coloring number. We prove that a graph $G$ with no K_{s,s}-subgraph and twin-width d has strong(weak) r-coloring numbers bounded by an exponential function of r and that we can construct graphs achieving such a dependency in r. One of the two central notions in structural theory of classes of sparse graphs is the classes with bounded expansion. These classes have strong algorithmic and structural properties and enjoy numerous characterizations and applications. Combinatorial discrepancy is a significant subject in its own right. It measures the inevitable irregularities of set systems and the inherent difficulty to approximate them. In this thesis, we give a new characterization of bounded expansion classes in terms of discrepancy of definable set systems. The notion of chi-boundedness is a central topic in chromatic graph theory. This thesis studies chi-bounded classes in the context of star colorings and, more generally, chi_p-colorings, say chi_s-bounded and (strongly and weakly) chi_p-bounded classes. This fits to a general scheme of sparsity and leads to natural extensions of the notion of bounded expansion class. Here we solve two conjectures related to star coloring ({i.e.} chi_2) boundedness and give structural characterizations of strongly chi_p-bounded classes and weakly chi_p-bounded classes
APA, Harvard, Vancouver, ISO, and other styles
10

Gajewar, Amita Surendra. "Approximate edge 3-coloring of cubic graphs." Thesis, Atlanta, Ga. : Georgia Institute of Technology, 2008. http://hdl.handle.net/1853/29735.

Full text
Abstract:
Thesis (M. S.)--Computing, Georgia Institute of Technology, 2009.
Committee Chair: Prof. Richard Lipton; Committee Member: Prof. Dana Randall; Committee Member: Prof. H. Venkateswaran. Part of the SMARTech Electronic Thesis and Dissertation Collection.
APA, Harvard, Vancouver, ISO, and other styles
More sources

Books on the topic "Graph coloring"

1

Jensen, Tommy R. Graph coloring problems. New York: Wiley, 1995.

Find full text
APA, Harvard, Vancouver, ISO, and other styles
2

Jensen, Tommy R. Graph coloring problems. New York: Wiley, 1995.

Find full text
APA, Harvard, Vancouver, ISO, and other styles
3

1946-, Kubale Marek, ed. Graph colorings. Providence, R.I: American Mathematical Society, 2004.

Find full text
APA, Harvard, Vancouver, ISO, and other styles
4

Chartrand, Gary. Chromatic graph theory. Boca Raton: Chapman & Hall/CRC, 2009.

Find full text
APA, Harvard, Vancouver, ISO, and other styles
5

de, Werra D., and Hertz A, eds. Graph colouring and variations. Amsterdam: North-Holland, 1989.

Find full text
APA, Harvard, Vancouver, ISO, and other styles
6

Barenboim, Leonid, and Michael Elkin. Distributed Graph Coloring. Cham: Springer International Publishing, 2013. http://dx.doi.org/10.1007/978-3-031-02009-4.

Full text
APA, Harvard, Vancouver, ISO, and other styles
7

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
APA, Harvard, Vancouver, ISO, and other styles
8

P, Hansen, and Marcotte Odile 1951-, eds. Graph colouring and applications. Providence, RI: American Mathematical Society, 1999.

Find full text
APA, Harvard, Vancouver, ISO, and other styles
9

Roy, Nelson, and Wilson Robin J, eds. Graph colourings. Essex, England: Longman Scientific & Technical, 1990.

Find full text
APA, Harvard, Vancouver, ISO, and other styles
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 text
APA, Harvard, Vancouver, ISO, and other styles
More sources

Book chapters on the topic "Graph coloring"

1

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
APA, Harvard, Vancouver, ISO, and other styles
2

Rahman, Md Saidur. "Graph Coloring." In Basic Graph Theory, 91–102. Cham: Springer International Publishing, 2017. http://dx.doi.org/10.1007/978-3-319-49475-3_7.

Full text
APA, Harvard, Vancouver, ISO, and other styles
3

Langberg, Michael, and Chandra Chekuri. "Graph Coloring." In Encyclopedia of Algorithms, 869–72. New York, NY: Springer New York, 2016. http://dx.doi.org/10.1007/978-1-4939-2864-4_170.

Full text
APA, Harvard, Vancouver, ISO, and other styles
4

Langberg, Michael, and Chandra Chekuri. "Graph Coloring." In Encyclopedia of Algorithms, 1–5. Boston, MA: Springer US, 2014. http://dx.doi.org/10.1007/978-3-642-27848-8_170-2.

Full text
APA, Harvard, Vancouver, ISO, and other styles
5

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 text
APA, Harvard, Vancouver, ISO, and other styles
6

Barenboim, Leonid, and Michael Elkin. "Defective Coloring." In Distributed Graph Coloring, 67–79. Cham: Springer International Publishing, 2013. http://dx.doi.org/10.1007/978-3-031-02009-4_6.

Full text
APA, Harvard, Vancouver, ISO, and other styles
7

Barenboim, Leonid, and Michael Elkin. "Basics of Graph Theory." In Distributed Graph Coloring, 7–27. Cham: Springer International Publishing, 2013. http://dx.doi.org/10.1007/978-3-031-02009-4_2.

Full text
APA, Harvard, Vancouver, ISO, and other styles
8

Barenboim, Leonid, and Michael Elkin. "Conclusion and Open Questions." In Distributed Graph Coloring, 143–48. Cham: Springer International Publishing, 2013. http://dx.doi.org/10.1007/978-3-031-02009-4_11.

Full text
APA, Harvard, Vancouver, ISO, and other styles
9

Barenboim, Leonid, and Michael Elkin. "Introduction." In Distributed Graph Coloring, 1–5. Cham: Springer International Publishing, 2013. http://dx.doi.org/10.1007/978-3-031-02009-4_1.

Full text
APA, Harvard, Vancouver, ISO, and other styles
10

Barenboim, Leonid, and Michael Elkin. "Basic Distributed Graph Coloring Algorithns." In Distributed Graph Coloring, 29–45. Cham: Springer International Publishing, 2013. http://dx.doi.org/10.1007/978-3-031-02009-4_3.

Full text
APA, Harvard, Vancouver, ISO, and other styles

Conference papers on the topic "Graph coloring"

1

Faria, Luerbio, Mauro Nigro, and Diana Sasaki. "On the conformable colorings of k-regular graphs." In Encontro de Teoria da Computação. Sociedade Brasileira de Computação - SBC, 2023. http://dx.doi.org/10.5753/etc.2023.230063.

Full text
Abstract:
In 1988, Chetwynd and Hilton defined conformable vertex colorings when trying to characterize the vertex colorings induced by a (∆ + 1)-total coloring. Anticonformable colorings were used to characterize the subcubic conformable graphs. A graph G is anticonformable if it has a (∆ + 1)-vertex coloring such that the number of color classes (including empty color classes) with the same parity as |V| is at most def(G) = ∑v∈V (∆− dG(v)). The only connected subcubic not anticonformable graph is the triangular prism graph L3. In this paper, we prove that if k is even, then every k-regular graph is not anticonformable; and if k ≥ 3 is odd, then there is a not anticonformable graph Hk, where H3 = L3.
APA, Harvard, Vancouver, ISO, and other styles
2

Adauto, Matheus N., Celina M. H. de Figueiredo, and Diana Sasaki. "Three Questions about Equitable Total Coloring of Small Cubic Graphs." In Encontro de Teoria da Computação. Sociedade Brasileira de Computação - SBC, 2022. http://dx.doi.org/10.5753/etc.2022.222596.

Full text
Abstract:
A total coloring assigns colors to the vertices and edges of a graph without conflicts and it is called equitable if the cardinalities of any two color classes differ by at most 1. In 2020, Stemock considered equitable total colorings of small cubic graphs and conjectured that every 4-total coloring of a cubic graph with less than 20 vertices is equitable. We present counterexamples to Stemock’s conjecture. We determine that every 4-total coloring must be equitable on all cubic graphs with 6, 8, 10, and 14 vertices. On the other hand, for cubic graphs with 12, 16, and 18 vertices, we characterize the color class configurations that might allow a non-equitable 4-total coloring. We prove that a cubic graph of 12 vertices is the smallest counterexample to Stemock’s conjecture.
APA, Harvard, Vancouver, ISO, and other styles
3

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 text
Abstract:
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.
APA, Harvard, Vancouver, ISO, and other styles
4

Domingues, Kenny, and Ana Silva. "On the Partial Grundy Number of a Graph Minus a Matching." In Encontro de Teoria da Computação. Sociedade Brasileira de Computação - SBC, 2022. http://dx.doi.org/10.5753/etc.2022.223134.

Full text
Abstract:
Given a k-coloring S1, . . . , Sk of G, a vertex in Si is said to be greedy if it has neighbors in Sj, for every j < i. Thus, a Grundy coloring can be seen as a coloring where every vertex is greedy. In contrast, a partial Grundy coloring is defined as a coloring in which each color class has at least one greedy vertex; the maximum number of colors in a partial Grundy coloring is denoted by ∂Γ(G). In this paper, we investigate some conjectures about Grundy colorings, already known not to hold, adapted to partial Grundy colorings. We prove that, while two of them also do not hold, a third does. Namely, that given a graph G and a matching M of G, we have that ∂Γ(G) ≤ 2∂Γ(G − M).
APA, Harvard, Vancouver, ISO, and other styles
5

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 text
APA, Harvard, Vancouver, ISO, and other styles
6

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
APA, Harvard, Vancouver, ISO, and other styles
7

Cruz, Mariana M. F. da, Celina M. H. de Figueiredo, Diana Sasaki, and Diane Castonguay. "On total coloring of small fullerene nanodiscs." In Encontro de Teoria da Computação. Sociedade Brasileira de Computação - SBC, 2023. http://dx.doi.org/10.5753/etc.2023.230129.

Full text
Abstract:
We investigate the total coloring of fullerene nanodiscs, a subclass of cubic planar graphs with girth 5 arising in Chemistry, motivated by a conjecture about the nonexistence of a Type 2 cubic graph of girth at least 5. We prove an auxiliary lemma which says that every central layer of a fullerene nanodisc is 4-total colorable, a necessary condition for the nanodisc to be Type 1, and we contribute by giving 4-total colorings for small fullerene nanodiscs, showing that these graphs are Type 1.
APA, Harvard, Vancouver, ISO, and other styles
8

Andrade, Davi de, and Ana Silva. "(Sub)Fall Coloring and B-Coloring Parameterized by Treewidth." In Encontro de Teoria da Computação. Sociedade Brasileira de Computação - SBC, 2022. http://dx.doi.org/10.5753/etc.2022.222982.

Full text
Abstract:
Given a proper coloring f of G, a vertex u is a b-vertex if it is adjacent to every color class distinct from its own. It is said to be a b-coloring if each color class contains at least one b-vertex, and a fall coloring if all vertices are b-vertices. Also, if f is a fall coloring of an induced subgraph H of G, then we say that f is a subfall coloring of G. In this paper, we provide algorithms for each of the decision problems related to these colorings whose running times are FPT when parameterized by the number of colors plus the treewidth of the input graph.
APA, Harvard, Vancouver, ISO, and other styles
9

De Loera, Jesús A., Susan Margulies, Michael Pernpeintner, Eric Riedl, David Rolnick, Gwen Spencer, Despina Stasi, and Jon Swenson. "Graph-Coloring Ideals." In ISSAC'15: International Symposium on Symbolic and Algebraic Computation. New York, NY, USA: ACM, 2015. http://dx.doi.org/10.1145/2755996.2756639.

Full text
APA, Harvard, Vancouver, ISO, and other styles
10

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 text
Abstract:
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.
APA, Harvard, Vancouver, ISO, and other styles

Reports on the topic "Graph coloring"

1

Jin, Zheming. Experience of Migrating Parallel Graph Coloring from CUDA to SYCL. Office of Scientific and Technical Information (OSTI), April 2022. http://dx.doi.org/10.2172/1864412.

Full text
APA, Harvard, Vancouver, ISO, and other styles
2

Jin, Zheming. Experience of Migrating Parallel Graph Coloring from CUDA to SYCL. Office of Scientific and Technical Information (OSTI), April 2022. http://dx.doi.org/10.2172/1864412.

Full text
APA, Harvard, Vancouver, ISO, and other styles
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
APA, Harvard, Vancouver, ISO, and other styles
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
APA, Harvard, Vancouver, ISO, and other styles
5

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
APA, Harvard, Vancouver, ISO, and other styles
6

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
APA, Harvard, Vancouver, ISO, and other styles
You might also be interested in the extended bibliographies on the topic 'Graph coloring' for particular source types:
Journal articles Dissertations / Theses Books
We offer discounts on all premium plans for authors whose works are included in thematic literature selections. Contact us to get a unique promo code!

To the bibliography