Relevant bibliographies by topics / Coloring graphs

Contents

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

Academic literature on the topic 'Coloring graphs'

Author: Grafiati
Published: 4 June 2021
Last updated: 4 February 2022

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 'Coloring graphs.'

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 "Coloring graphs"

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 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
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 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
3

McATEE, JENELLE, DANIEL S. SILVER, and SUSAN G. WILLIAMS. "COLORING SPATIAL GRAPHS." Journal of Knot Theory and Its Ramifications 10, no. 01 (February 2001): 109–20. http://dx.doi.org/10.1142/s0218216501000755.

Full text
Abstract:
Coloring invariants for spatial graphs are defined, inspired by Fox colorings of knots and links. A new proof of a the nontriviality of Suzuki's n-theta curves is given. Necessary and sufficient conditions for colorings of θn-curves are described in terms of an Alexander polynomial defined by Litherland.
APA, Harvard, Vancouver, ISO, and other styles
4

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

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
7

GANDHI, RAJIV, BRADFORD GREENING, SRIRAM PEMMARAJU, and RAJIV RAMAN. "SUB-COLORING AND HYPO-COLORING INTERVAL GRAPHS." Discrete Mathematics, Algorithms and Applications 02, no. 03 (September 2010): 331–45. http://dx.doi.org/10.1142/s1793830910000693.

Full text
Abstract:
In this paper, we study the sub-coloring and hypo-coloring problems on interval graphs. These problems have applications in job scheduling and distributed computing and can be used as "subroutines" for other combinatorial optimization problems. In the sub-coloring problem, given a graph G, we want to partition the vertices of G into minimum number of sub-color classes, where each sub-color class induces a union of disjoint cliques in G. In the hypo-coloring problem, given a graph G, and integral weights on vertices, we want to find a partition of the vertices of G into sub-color classes such that the sum of the weights of the heaviest cliques in each sub-color class is minimized. We present a "forbidden subgraph" characterization of graphs with sub-chromatic number k and use this to derive a 3-approximation algorithm for sub-coloring interval graphs. For the hypo-coloring problem on interval graphs, we first show that it is NP-complete, and then via reduction to the max-coloring problem, show how to obtain an O( log n)-approximation algorithm for it.
APA, Harvard, Vancouver, ISO, and other styles
8

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
9

Durgun, Derya, and Busra Ozen-Dortok. "Packing chromatic number of transformation graphs." Thermal Science 23, Suppl. 6 (2019): 1991–95. http://dx.doi.org/10.2298/tsci190720363d.

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

Sudev, N. K., K. P. Chithra, K. A. Germina, S. Satheesh, and Johan Kok. "On certain coloring parameters of Mycielski graphs of some graphs." Discrete Mathematics, Algorithms and Applications 10, no. 03 (June 2018): 1850030. http://dx.doi.org/10.1142/s1793830918500301.

Full text
Abstract:
Coloring the vertices of a graph [Formula: see text] according to certain conditions can be considered as a random experiment and a discrete random variable [Formula: see text] can be defined as the number of vertices having a particular color in the proper coloring of [Formula: see text]. The concepts of mean and variance, two important statistical measures, have also been introduced to the theory of graph coloring and determined the values of these parameters for a number of standard graphs. In this paper, we discuss the coloring parameters of the Mycielskian of certain standard graphs.
APA, Harvard, Vancouver, ISO, and other styles
More sources

Dissertations / Theses on the topic "Coloring graphs"

1

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
2

Montgomery, Bruce Lee. "Dynamic coloring of graphs." Morgantown, W. Va. : [West Virginia University Libraries], 2001. http://etd.wvu.edu/templates/showETD.cfm?recnum=2109.

Full text
Abstract:
Thesis (Ph. D.)--West Virginia University, 2001.
Title from document title page. Document formatted into pages; contains viii, 52 p. : ill. Vita. Includes abstract. Includes bibliographical references (p. 51).
APA, Harvard, Vancouver, ISO, and other styles
3

Tahraoui, Mohammed Amin. "Coloring, packing and embedding of graphs." Phd thesis, Université Claude Bernard - Lyon I, 2012. http://tel.archives-ouvertes.fr/tel-00995041.

Full text
Abstract:
In this thesis, we investigate some problems in graph theory, namelythe graph coloring problem, the graph packing problem and tree pattern matchingfor XML query processing. The common point between these problems is that theyuse labeled graphs.In the first part, we study a new coloring parameter of graphs called the gapvertex-distinguishing edge coloring. It consists in an edge-coloring of a graph G whichinduces a vertex distinguishing labeling of G such that the label of each vertex isgiven by the difference between the highest and the lowest colors of its adjacentedges. The minimum number of colors required for a gap vertex-distinguishing edgecoloring of G is called the gap chromatic number of G and is denoted by gap(G).We will compute this parameter for a large set of graphs G of order n and we evenprove that gap(G) 2 fn E 1; n; n + 1g.In the second part, we focus on graph packing problems, which is an area ofgraph theory that has grown significantly over the past several years. However, themajority of existing works focuses on unlabeled graphs. In this thesis, we introducefor the first time the packing problem for a vertex labeled graph. Roughly speaking,it consists of graph packing which preserves the labels of the vertices. We studythe corresponding optimization parameter on several classes of graphs, as well asfinding general bounds and characterizations.The last part deal with the query processing of a core subset of XML query languages:XML twig queries. An XML twig query, represented as a small query tree,is essentially a complex selection on the structure of an XML document. Matching atwig query means finding all the occurrences of the query tree embedded in the XMLdata tree. Many holistic twig join algorithms have been proposed to match XMLtwig pattern. Most of these algorithms find twig pattern matching in two steps. Inthe first one, a query tree is decomposed into smaller pieces, and solutions againstthese pieces are found. In the second step, all of these partial solutions are joinedtogether to generate the final solutions. In this part, we propose a novel holistictwig join algorithm, called TwigStack++, which features two main improvementsin the decomposition and matching phase. The proposed solutions are shown to beefficient and scalable, and should be helpful for the future research on efficient queryprocessing in a large XML database.
APA, Harvard, Vancouver, ISO, and other styles
4

Yerger, Carl Roger Jr. "Color-critical graphs on surfaces." Diss., Georgia Institute of Technology, 2010. http://hdl.handle.net/1853/37197.

Full text
Abstract:
A graph is (t+1)-critical if it is not t-colorable, but every proper subgraph is. In this thesis, we study the structure of critical graphs on higher surfaces. One major result in this area is Carsten Thomassen's proof that there are finitely many 6-critical graphs on a fixed surface. This proof involves a structural theorem about a precolored cycle C of length q. In general terms, he proves that a coloring, c, of C, can be extended inside the cycle, or there exists a subgraph H with at most a number of vertices exponential in q such that c can not be extended to a 5-coloring of H. In Chapter 2, we proved an alternative proof that reduces the number of vertices in H to be cubic in q. In Chapter 3, we find the nine 6-critical graphs among all graphs embeddable on the Klein bottle. In Chapter 4, we prove a result concerning critical graphs related to an analogue of Steinberg's conjecture for higher surfaces. We show that if G is a 4-critical graph embedded on surface S, with Euler genus g and has no cycles of length four through ten, then G has at most 2442g + 37 vertices.
APA, Harvard, Vancouver, ISO, and other styles
5

Fowler, Thomas George. "Unique coloring of planar graphs." Diss., Georgia Institute of Technology, 1998. http://hdl.handle.net/1853/30358.

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

Salavatipour, Mohammadreza. "On sum coloring of graphs." Thesis, National Library of Canada = Bibliothèque nationale du Canada, 2000. http://www.collectionscanada.ca/obj/s4/f2/dsk1/tape3/PQDD_0023/MQ50369.pdf.

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

Sengupta, Rik. "List coloring in general graphs." Thesis, Massachusetts Institute of Technology, 2015. http://hdl.handle.net/1721.1/112878.

Full text
Abstract:
Thesis: S.M., Massachusetts Institute of Technology, Department of Mathematics, 2015.
Cataloged from PDF version of thesis.
Includes bibliographical references (pages 30-31).
In this thesis we explore some of the relatively new approaches to the problem of list-coloring graphs. This is a problem that has its roots in classical graph theory, but has developed an entire theory of its own, that uses tools from structural graph theory, probabilistic approaches, as well as heuristic and algorithmic approaches. This thesis details two approaches one can take to understand list-coloring and prove results for several classes of graphs; one of them is to use the idea of graph kernels, and the other is to look at list-edge-coloring. In this thesis we present the state-of-the-art research on these two problems. We begin by setting up definitions and preliminaries, and then go into each of these two topics in turn. Along the way we briefly mention some of the very new research on the topics, including some new approaches developed for the purpose of writing this thesis. We finish with a survey of some of the major open problems that still remain in the area.
by Rik Sengupta.
S.M.
APA, Harvard, Vancouver, ISO, and other styles
8

Kurt, Oguz. "On The Coloring of Graphs." The Ohio State University, 2009. http://rave.ohiolink.edu/etdc/view?acc_num=osu1262287401.

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

Song, Zengmin. "Cycles and coloring in graphs." HKBU Institutional Repository, 2001. http://repository.hkbu.edu.hk/etd_ra/285.

Full text
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 "Coloring graphs"

1

Yap, H. P. Total colourings of graphs. Berlin: Springer, 1996.

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

Salavatipour, Mohammadreza. On sum coloring of graphs. Toronto: University of Toronto, Dept. of Computer Science, 2000.

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

Koh, K. M. (Khee Meng), 1944- and Teo K. L, eds. Chromatic polynomials and chromaticity of graphs. Singapore: World Scientific Pub., 2005.

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

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
5

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

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

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

Find 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

Kubale, Marek, ed. Graph Colorings. Providence, Rhode Island: American Mathematical Society, 2004. http://dx.doi.org/10.1090/conm/352.

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

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

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

Zhang, Ping. Color-Induced Graph Colorings. Cham: Springer International Publishing, 2015. http://dx.doi.org/10.1007/978-3-319-20394-2.

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

Book chapters on the topic "Coloring graphs"

1

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

Fürer, Martin, and C. R. Subramanian. "Coloring random graphs." In Algorithm Theory — SWAT '92, 284–91. Berlin, Heidelberg: Springer Berlin Heidelberg, 1992. http://dx.doi.org/10.1007/3-540-55706-7_24.

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

Kierstead, Hal A. "Coloring graphs on-line." In Online Algorithms, 281–305. Berlin, Heidelberg: Springer Berlin Heidelberg, 1998. http://dx.doi.org/10.1007/bfb0029574.

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

Coja-Oghlan, Amin. "Coloring Semirandom Graphs Optimally." In Automata, Languages and Programming, 383–95. Berlin, Heidelberg: Springer Berlin Heidelberg, 2004. http://dx.doi.org/10.1007/978-3-540-27836-8_34.

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

Lovász, L., J. Pelikán, and K. Vesztergombi. "Coloring Maps and Graphs." In Discrete Mathematics, 197–210. New York, NY: Springer New York, 2003. http://dx.doi.org/10.1007/0-387-21777-0_13.

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

Aigner, Martin, and Günter M. Ziegler. "Five-coloring plane graphs." In Proofs from THE BOOK, 161–64. Berlin, Heidelberg: Springer Berlin Heidelberg, 1998. http://dx.doi.org/10.1007/978-3-662-22343-7_25.

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

Kun, Jeremy, and Lev Reyzin. "On Coloring Resilient Graphs." In Mathematical Foundations of Computer Science 2014, 517–28. Berlin, Heidelberg: Springer Berlin Heidelberg, 2014. http://dx.doi.org/10.1007/978-3-662-44465-8_44.

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

Bodlaender, Hans L., Ton Kloks, Richard B. Tan, and Jan van Leeuwen. "λ-Coloring of Graphs." In STACS 2000, 395–406. Berlin, Heidelberg: Springer Berlin Heidelberg, 2000. http://dx.doi.org/10.1007/3-540-46541-3_33.

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

Gärtner, Bernd, and Jiří Matoušek. "Coloring 3-Chromatic Graphs." In Approximation Algorithms and Semidefinite Programming, 157–66. Berlin, Heidelberg: Springer Berlin Heidelberg, 2011. http://dx.doi.org/10.1007/978-3-642-22015-9_9.

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

Aigner, Martin, and Günter M. Ziegler. "Five-coloring plane graphs." In Proofs from THE BOOK, 227–30. Berlin, Heidelberg: Springer Berlin Heidelberg, 2010. http://dx.doi.org/10.1007/978-3-642-00856-6_34.

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

Conference papers on the topic "Coloring graphs"

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

Dvořák, Zdeněk, and Ken-ichi Kawarabayashi. "List-coloring embedded graphs." In Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms. Philadelphia, PA: Society for Industrial and Applied Mathematics, 2013. http://dx.doi.org/10.1137/1.9781611973105.72.

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

Bradonjić, Milan, Tobias Müller, and Allon G. Percus. "Coloring Geographical Threshold Graphs." In 2009 Proceedings of the Sixth Workshop on Analytic Algorithmics and Combinatorics (ANALCO). Philadelphia, PA: Society for Industrial and Applied Mathematics, 2009. http://dx.doi.org/10.1137/1.9781611972993.2.

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

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

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

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

Karthikeyan, S., and U. Mary. "On b-coloring and Johan coloring of line graphs." In PROCEEDINGS OF INTERNATIONAL CONFERENCE ON ADVANCES IN MATERIALS RESEARCH (ICAMR - 2019). AIP Publishing, 2020. http://dx.doi.org/10.1063/5.0016874.

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

Robertson, Neil, Daniel P. Sanders, Paul Seymour, and Robin Thomas. "Efficiently four-coloring planar graphs." In the twenty-eighth annual ACM symposium. New York, New York, USA: ACM Press, 1996. http://dx.doi.org/10.1145/237814.238005.

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

Reports on the topic "Coloring graphs"

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
APA, Harvard, Vancouver, ISO, and other styles
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
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
You might also be interested in the extended bibliographies on the topic 'Coloring graphs' 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