Relevant bibliographies by topics / Graph colouring

Contents

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

Academic literature on the topic 'Graph colouring'

Author: Grafiati
Published: 4 June 2021
Last updated: 8 June 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 colouring.'

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 colouring"

1

LEHNER, FLORIAN. "Random Colourings and Automorphism Breaking in Locally Finite Graphs." Combinatorics, Probability and Computing 22, no. 6 (September 16, 2013): 885–909. http://dx.doi.org/10.1017/s0963548313000382.

Full text
Abstract:
A colouring of a graphGis called distinguishing if its stabilizer in AutGis trivial. It has been conjectured that, if every automorphism of a locally finite graph moves infinitely many vertices, then there is a distinguishing 2-colouring. We study properties of random 2-colourings of locally finite graphs and show that the stabilizer of such a colouring is almost surely nowhere dense in AutGand a null set with respect to the Haar measure on the automorphism group. We also investigate random 2-colourings in several classes of locally finite graphs where the existence of a distinguishing 2-colouring has already been established. It turns out that in all of these cases a random 2-colouring is almost surely distinguishing.
APA, Harvard, Vancouver, ISO, and other styles
2

Madaras, Tomáš, and Mária Šurimová. "Facial Homogeneous Colouring of Graphs." Symmetry 13, no. 7 (July 6, 2021): 1213. http://dx.doi.org/10.3390/sym13071213.

Full text
Abstract:
A proper colouring of a plane graph G is called facially homogeneous if it uses the same number of colours for every face of G. We study various sufficient conditions of facial homogeneous colourability of plane graphs, its relation to other facial colourings, and the extension of this concept for embedded graphs in general.
APA, Harvard, Vancouver, ISO, and other styles
3

Voloshin, V. "A note on the conditional chromatic polynomial." Glasgow Mathematical Journal 36, no. 3 (September 1994): 265–67. http://dx.doi.org/10.1017/s0017089500030834.

Full text
Abstract:
In this note we consider a finite graph without loops and multiple edges. The colouring of a graph G in λ colours is the colouring of its vertices in such a way that no two of adjacent vertices have the same colours and the number of used colours does not exceed λ [1, 4]. Two colourings of graph G are called different if there exists at least one vertex which changes colour when passing from one colouring to another.
APA, Harvard, Vancouver, ISO, and other styles
4

V, Kaviyaa, and Manikandan M. "Characterization of a Vertex Colouring of a Double Layered Complete Fuzzy Graph Using ? – CUT." International Journal for Research in Applied Science and Engineering Technology 10, no. 11 (November 30, 2022): 1367–73. http://dx.doi.org/10.22214/ijraset.2022.47510.

Full text
Abstract:
Abstract: In this paper we defined a new fuzzy graph named Double layered complete fuzzy graph. (DLCFG). The double layered complete fuzzy graph gives a 3-D structure. Further we introduced vertex colouring of the double layered complete fuzzy graph using α-cut. Keywords: Graph theory, Fuzzy graph, colouring of graphs, double layered fuzzy graph, complete fuzzy graph, alpha cut, colouring of double layered fuzzy graph, colouring of double layered complete fuzzy using alpha cut.
APA, Harvard, Vancouver, ISO, and other styles
5

Bednarz, Urszula, Iwona Włoch, and Małgorzata Wołowiec-Musiał. "Total Graph Interpretation of the Numbers of the Fibonacci Type." Journal of Applied Mathematics 2015 (2015): 1–7. http://dx.doi.org/10.1155/2015/837917.

Full text
Abstract:
We give a total graph interpretation of the numbers of the Fibonacci type. This graph interpretation relates to an edge colouring by monochromatic paths in graphs. We will show that it works for almost all numbers of the Fibonacci type. Moreover, we give the lower bound and the upper bound for the number of all(A1,2A1)-edge colourings in trees.
APA, Harvard, Vancouver, ISO, and other styles
6

JUKNA, S., and G. SCHNITGER. "Triangle-Freeness is Hard to Detect." Combinatorics, Probability and Computing 11, no. 6 (November 2002): 549–69. http://dx.doi.org/10.1017/s0963548302005333.

Full text
Abstract:
We show that recognizing the K3-freeness and K4-freeness of graphs is hard, respectively, for two-player nondeterministic communication protocols using exponentially many partitions and for nondeterministic syntactic read-r times branching programs.The key ingredient is a generalization of a colouring lemma, due to Papadimitriou and Sipser, which says that for every balanced red—blue colouring of the edges of the complete n-vertex graph there is a set of εn2 triangles, none of which is monochromatic, such that no triangle can be formed by picking edges from different triangles. We extend this lemma to exponentially many colourings and to partial colourings.
APA, Harvard, Vancouver, ISO, and other styles
7

Bard, Stefan, Gary MacGillivray, and Shayla Redlin. "The complexity of frugal colouring." Arabian Journal of Mathematics 10, no. 1 (January 29, 2021): 51–57. http://dx.doi.org/10.1007/s40065-021-00311-7.

Full text
Abstract:
AbstractA t-frugal colouring of a graph G is an assignment of colours to the vertices of G, such that each colour appears at most t times in the neighbourhood of any vertex. A dichotomy theorem for the complexity of deciding whether a graph has a 1-frugal colouring with k colours was found by McCormick and Thomas, and then later extended to restricted graph classes by Kratochvil and Siggers. We generalize the McCormick and Thomas theorem by proving a dichotomy theorem for the complexity of deciding whether a graph has a t-frugal colouring with k colours, for all pairs of positive integers t and k. We also generalize bounds of Lih et al. for the number of colours needed in a 1-frugal colouring of a given $$K_4$$ K 4 -minor-free graph with maximum degree $$\Delta $$ Δ to t-frugal colourings, for any positive integer t.
APA, Harvard, Vancouver, ISO, and other styles
8

Sudheer, Niranjana, Ann Cherian George, Achu Aniyan, and Sudev Naduvath. "Some new results on colour-induced signed graphs." Acta Universitatis Sapientiae, Informatica 14, no. 2 (December 1, 2022): 338–53. http://dx.doi.org/10.2478/ausi-2022-0019.

Full text
Abstract:
Abstract A signed graph is a graph in which positive or negative signs are assigned to its edges. We consider equitable colouring and Hamiltonian colouring to obtain induced signed graphs. An equitable colour-induced signed graph is a signed graph constructed from a given graph in which each edge uv receives a sign (−1)|c(v)−c(u)|,where c is an equitable colouring of vertex v. A Hamiltonian colour-induced signed graph is a signed graph obtained from a graph G in which for each edge e = uv, the signature function σ(uv)=(−1)|c(v)−c(u)|, gives a sign such that, |c(u)− c(v)| ≥ n − 1 − D(u, v) where c is a function that assigns a colour to each vertex satisfying the given condition. This paper discusses the properties and characteristics of signed graphs induced by the equitable and Hamiltonian colouring of graphs.
APA, Harvard, Vancouver, ISO, and other styles
9

KIERSTEAD, H. A., and A. V. KOSTOCHKA. "A Short Proof of the Hajnal–Szemerédi Theorem on Equitable Colouring." Combinatorics, Probability and Computing 17, no. 2 (March 2008): 265–70. http://dx.doi.org/10.1017/s0963548307008619.

Full text
Abstract:
A proper vertex colouring of a graph is equitable if the sizes of colour classes differ by at most one. We present a new shorter proof of the celebrated Hajnal–Szemerédi theorem: for every positive integer r, every graph with maximum degree at most r has an equitable colouring with r+1 colours. The proof yields a polynomial time algorithm for such colourings.
APA, Harvard, Vancouver, ISO, and other styles
10

Harary, Frank, and Zsolt Tuza. "Two graph-colouring games." Bulletin of the Australian Mathematical Society 48, no. 1 (August 1993): 141–49. http://dx.doi.org/10.1017/s0004972700015549.

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

Dissertations / Theses on the topic "Graph colouring"

1

Rackham, Tom. "Problems in graph colouring." Thesis, University of Oxford, 2009. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.526104.

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

Williams, Jini. "Aspects of graph colouring." Thesis, Open University, 2004. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.410449.

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

Ferguson, David G. "Topics in graph colouring and graph structures." Thesis, London School of Economics and Political Science (University of London), 2013. http://etheses.lse.ac.uk/735/.

Full text
Abstract:
This thesis investigates problems in a number of different areas of graph theory. These problems are related in the sense that they mostly concern the colouring or structure of the underlying graph. The first problem we consider is in Ramsey Theory, a branch of graph theory stemming from the eponymous theorem which, in its simplest form, states that any sufficiently large graph will contain a clique or anti-clique of a specified size. The problem of finding the minimum size of underlying graph which will guarantee such a clique or anti-clique is an interesting problem in its own right, which has received much interest over the last eighty years but which is notoriously intractable. We consider a generalisation of this problem. Rather than edges being present or not present in the underlying graph, each is assigned one of three possible colours and, rather than considering cliques, we consider cycles. Combining regularity and stability methods, we prove an exact result for a triple of long cycles. We then move on to consider removal lemmas. The classic Removal Lemma states that, for n sufficiently large, any graph on n vertices containing o(n^3) triangles can be made triangle-free by the removal of o(n^2) edges. Utilising a coloured hypergraph generalisation of this result, we prove removal lemmas for two classes of multinomials. Next, we consider a problem in fractional colouring. Since finding the chromatic number of a given graph can be viewed as an integer programming problem, it is natural to consider the solution to the corresponding linear programming problem. The solution to this LP-relaxation is called the fractional chromatic number. By a probabilistic method, we improve on the best previously known bound for the fractional chromatic number of a triangle-free graph with maximum degree at most three. Finally, we prove a weak version of Vizing's Theorem for hypergraphs. We prove that, if H is an intersecting 3-uniform hypergraph with maximum degree D and maximum multiplicity m, then H has at most 2D+m edges. Furthermore, we prove that the unique structure achieving this maximum is m copies of the Fano Plane.
APA, Harvard, Vancouver, ISO, and other styles
4

Watts, Ivor Llewellyn. "Overlap and fractional graph colouring." Thesis, Open University, 2009. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.505353.

Full text
Abstract:
Although a considerable body of material exists concerning the colouring of graphs, there is much less on overlap colourings. In this thesis, we investigate the colouring of certain families of graphs.
APA, Harvard, Vancouver, ISO, and other styles
5

Waters, Robert James. "Graph colouring and frequency assignment." Thesis, University of Nottingham, 2005. http://eprints.nottingham.ac.uk/10135/.

Full text
Abstract:
In this thesis we study some graph colouring problems which arise from mathematical models of frequency assignment in radiocommunications networks, in particular from models formulated by Hale and by Tesman in the 1980s. The main body of the thesis is divided into four chapters. Chapter 2 is the shortest, and is largely self-contained; it contains some early work on the frequency assignment problem, in which each edge of a graph is assigned a positive integer weight, and an assignment of integer colours to the vertices is sought in which the colours of adjacent vertices differ by at least the weight of the edge joining them. The remaining three chapters focus on problems which combine frequency assignment with list colouring, in which each vertex has a list of integers from which its colour must be chosen. In Chapter 3 we study list colourings where the colours of adjacent vertices must differ by at least a fixed integer s, and in Chapter 4 we add the additional restriction that the lists must be sets of consecutive integers. In both cases we investigate the required size of the lists so that a colouring can always be found. By considering the behaviour of these parameters as s tends to infinity, we formulate continuous analogues of the two problems, considering lists which are real intervals in Chapter 4, and arbitrary closed real sets in Chapter 5. This gives rise to two new graph invariants, the consecutive choosability ratio tau(G) and the choosability ratio sigma(G). We relate these to other known graph invariants, provide general bounds on their values, and determine specific values for various classes of graphs.
APA, Harvard, Vancouver, ISO, and other styles
6

Song, Jian. "Graph colouring with input restrictions." Thesis, Durham University, 2013. http://etheses.dur.ac.uk/6998/.

Full text
Abstract:
In this thesis, we research the computational complexity of the graph colouring problem and its variants including precolouring extension and list colouring for graph classes that can be characterised by forbidding one or more induced subgraphs. We investigate the structural properties of such graph classes and prove a number of new properties. We then consider to what extent these properties can be used for efficiently solving the three types of colouring problems on these graph classes. In some cases we obtain polynomial-time algorithms, whereas other cases turn out to be NP-complete. We determine the computational complexity of k-COLOURING, k-PRECOLOURING EXTENSION and LIST k-COLOURING on $P_k$-free graphs. In particular, we prove that k-COLOURING on $P_8$-free graphs is NP-complete, 4-PRECOLOURING EXTENSION $P_7$-free graphs is NP-complete, and LIST 4-COLOURING on $P_6$-free graphs is NP-complete. In addition, we show the existence of an integer r such that k-COLOURING is NP-complete for $P_r$-free graphs with girth 4. In contrast, we determine for any fixed girth $g\geq 4$ a lower bound $r(g)$ such that every $P_{r(g)}$-free graph with girth at least $g$ is 3-colourable. We also prove that 3-LIST COLOURING is NP-complete for complete graphs minus a matching. We present a polynomial-time algorithm for solving 4-PRECOLOURING EXTENSION on $(P_2+P_3)$-free graphs, a polynomial-time algorithm for solving LIST 3-Colouring on $(P_2+P_4)$-free graphs, and a polynomial-time algorithm for solving LIST 3-COLOURING on $sP_3$-free graphs. We prove that LIST k-COLOURING for $(K_{s,t},P_r)$-free graphs is also polynomial-time solvable. We obtain several new dichotomies by combining the above results with some known results.
APA, Harvard, Vancouver, ISO, and other styles
7

Feghali, Carl. "Topics in graph colouring and extremal graph theory." Thesis, Durham University, 2016. http://etheses.dur.ac.uk/11790/.

Full text
Abstract:
In this thesis we consider three problems related to colourings of graphs and one problem in extremal graph theory. Let $G$ be a connected graph with $n$ vertices and maximum degree $\Delta(G)$. Let $R_k(G)$ denote the graph with vertex set all proper $k$-colourings of $G$ and two $k$-colourings are joined by an edge if they differ on the colour of exactly one vertex. Our first main result states that $R_{\Delta(G)+1}(G)$ has a unique non-trivial component with diameter $O(n^2)$. This result can be viewed as a reconfigurations analogue of Brooks' Theorem and completes the study of reconfigurations of colourings of graphs with bounded maximum degree. A Kempe change is the operation of swapping some colours $a$, $b$ of a component of the subgraph induced by vertices with colour $a$ or $b$. Two colourings are Kempe equivalent if one can be obtained from the other by a sequence of Kempe changes. Our second main result states that all $\Delta(G)$-colourings of a graph $G$ are Kempe equivalent unless $G$ is the complete graph or the triangular prism. This settles a conjecture of Mohar (2007). Motivated by finding an algorithmic version of a structure theorem for bull-free graphs due to Chudnovsky (2012), we consider the computational complexity of deciding if the vertices of a graph can be partitioned into two parts such that one part is triangle-free and the other part is a collection of complete graphs. We show that this problem is NP-complete when restricted to five classes of graphs (including bull-free graphs) while polynomial-time solvable for the class of cographs. Finally we consider a graph-theoretic version formulated by Holroyd, Spencer and Talbot (2007) of the famous Erd\H{o}s-Ko-Rado Theorem in extremal combinatorics and obtain some results for the class of trees.
APA, Harvard, Vancouver, ISO, and other styles
8

Farrugia, Alastair. "Uniqueness and Complexity in Generalised Colouring." Thesis, University of Waterloo, 2003. http://hdl.handle.net/10012/1018.

Full text
Abstract:
The study and recognition of graph families (or graph properties) is an essential part of combinatorics. Graph colouring is another fundamental concept of graph theory that can be looked at, in large part, as the recognition of a family of graphs that are colourable according to certain rules. In this thesis, we study additive induced-hereditary families, and some generalisations, from a colouring perspective. Our main results are: · Additive induced-hereditary families are uniquely factorisable into irreducible families. · If P and Q are additive induced-hereditary graph families, then (P,Q)-COLOURING is NP-hard, with the exception of GRAPH 2-COLOURING. Moreover, with the same exception, (P,Q)-COLOURING is NP-complete iff P- and Q-RECOGNITION are both in NP. This proves a 1997 conjecture of Kratochvíl and Schiermeyer. We also provide generalisations to somewhat larger families. Other results that we prove include: · a characterisation of the minimal forbidden subgraphs of a hereditary property in terms of its minimal forbidden induced-subgraphs, and vice versa; · extensions of Mihók's construction of uniquely colourable graphs, and Scheinerman's characterisations of compositivity, to disjoint compositive properties; · an induced-hereditary property has at least two factorisations into arbitrary irreducible properties, with an explicitly described set of exceptions; · if G is a generating set for A ο B, where A and B are indiscompositive, then we can extract generating sets for A and B using a greedy algorithm.
APA, Harvard, Vancouver, ISO, and other styles
9

Chowdhury, Ameerah. "Colouring Subspaces." Thesis, University of Waterloo, 2005. http://hdl.handle.net/10012/1026.

Full text
Abstract:
This thesis was originally motivated by considering vector space analogues of problems in extremal set theory, but our main results concern colouring a graph that is intimately related to these vector space analogues. The vertices of the q-Kneser graph are the k-dimensional subspaces of a vector space of dimension v over Fq, and two k-subspaces are adjacent if they have trivial intersection. The new results in this thesis involve colouring the q-Kneser graph when k=2. There are two cases. When k=2 and v=4, the chromatic number is q2+q. If k=2 and v>4, the chromatic number is (q(v-1)-1)/(q-1). In both cases, we characterise the minimal colourings. We develop some theory for colouring the q-Kneser graph in general.
APA, Harvard, Vancouver, ISO, and other styles
10

Rocha, Leonardo Sampaio. "Algorithmic aspects of graph colouring heuristics." Nice, 2012. https://tel.archives-ouvertes.fr/tel-00759408.

Full text
Abstract:
Une coloration propre d’un graphe est une fonction qui attribue une couleur à chaque sommet du graphe avec la restriction que deux sommets voisins ont des couleurs distinctes. Les colorations permettent de modéliser des problèmes d’ordonnancement, d’allocation de fréquences ou de registres. Le problème de trouver une coloration propre d’un graphe qui minimise le nombre de couleurs est un problème NP-difficile très connu. Dans cette thèse nous étudions le nombre de Grundy et le nombre b-chromatique des graphes, deux paramètres qui permettent d’évaluer quelques heuristiques pour le problème d’e la coloration propre. Nous commençons par dresser un état de l’art des résultats sur ces deux paramètres. Puis nous montrons que déterminer le nombre de Grundy est NP-difficile pour un graphe cordal et polynomial sur le graphe sans P5 bipartis. Ensuite nous montrons que déterminer le nombre b-chromatique est NP-difficile pour un graphe cordal et distance-héréditaire, et nous donnons des algorithmes polynomiaux pour certaines sous-classes de graphes blocs, complémentaires des graphes bipartis et P4-sparses. Nous considérons également la complexité à paramètre fixé de déterminer le nombre de Grundy (resp. Nombre b-chromatique) et en particulier, nous montrons que décider sir le nombre de Grundy (ou le nombre b-chromatique) d’un graphe G est au moins V(G)-k admet un algorithme FPT lorsque k est le paramètre. Enfin, nous considérons la complexité de nombreux problèmes liés à la comparaison du nombre de Grundy et nombre b-chromatique avec divers autres paramètres d’un graphe
A proper coloring of a graph is a function that assigns a color to each vertex with the restriction that adjacent vertices are assigned with distinct colors. Proper colorings are a natural model for many problems, like scheduling, frequency assignment and register allocation. The problem of finding a proper coloring of a graph with the minimum number of colors is a well-known NP-hard problem. In this thesis we study the Grundy number and the b-chromatic number of graphs, two parameters that evaluate some heuristics for finding proper colorings. We start by giving the state of the art of the results about these parameters. Then, we show that the problem of determining the Grundy Number of bipartite or chordal graphs is NP-hard, but it is solvable in polynomial time for P5-free bipartite graphs. After, we show that the problem of determining the b-chromatic number or a chordal distance-hereditary graph is NP-hard, and we give polynomial-time algorithms for some subclasses of block graphs, complement of bipartite graphs and p4-sparse graphs. We also consider the fixed-parameter tractability of determining the Grundy number and the b-chromatic number, and in particular we show that deciding if the Grundy number (or the b-chromatic number) of a graph G is at least V(G)-k admits an FPT algorithm when k is the parameter. Finally, we consider the computational complexity of many problems related to comparing the b-chromatic number and the Grundy number with various other related parameter of a graph
APA, Harvard, Vancouver, ISO, and other styles
More sources

Books on the topic "Graph colouring"

1

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
2

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
3

Lewis, R. M. R. Guide to Graph Colouring. Cham: Springer International Publishing, 2021. http://dx.doi.org/10.1007/978-3-030-81054-2.

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

Lewis, R. M. R. A Guide to Graph Colouring. Cham: Springer International Publishing, 2016. http://dx.doi.org/10.1007/978-3-319-25730-3.

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

Molloy, Michael, and Bruce Reed. Graph Colouring and the Probabilistic Method. Berlin, Heidelberg: Springer Berlin Heidelberg, 2002. http://dx.doi.org/10.1007/978-3-642-04016-0.

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

A, Reed Bruce, ed. Graph colouring and the probabilistic method. Berlin: Springer, 2002.

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

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
8

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

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

Workshop on Cycles and Colourings (6th 1997 Stará Lesná, Slovakia). Cycles and colourings '97: Proceedings of the 6th Workshop on Cycles and Colourings, Stará Lesná, September 7-12, 1997. Edited by Harant Jochen. Bratislava: Mathematical Institute, Slovak Academy of Sciences, 1999.

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

Brown, Jason Ira. A theory of generalized graph colourings. Toronto: [s.n.], 1987.

Find full text
APA, Harvard, Vancouver, ISO, and other styles
More sources

Book chapters on the topic "Graph colouring"

1

Diestel, Reinhard. "Colouring." In Graph Theory, 119–48. Berlin, Heidelberg: Springer Berlin Heidelberg, 2017. http://dx.doi.org/10.1007/978-3-662-53622-3_5.

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

Diestel, Reinhard. "Colouring." In Graph Theory, 117–44. Berlin, Heidelberg: Springer Berlin Heidelberg, 2005. http://dx.doi.org/10.1007/978-3-642-14279-6_5.

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

Bollobás, Béla. "Colouring." In Modern Graph Theory, 145–79. New York, NY: Springer New York, 1998. http://dx.doi.org/10.1007/978-1-4612-0619-4_5.

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

Henning, Michael A., and Jan H. van Vuuren. "Graph colouring." In Graph and Network Theory, 449–500. Cham: Springer International Publishing, 2022. http://dx.doi.org/10.1007/978-3-031-03857-0_14.

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

Ball, Simeon, and Oriol Serra. "Graph Colouring." In Compact Textbooks in Mathematics, 127–42. Cham: Springer Nature Switzerland, 2024. http://dx.doi.org/10.1007/978-3-031-55384-4_8.

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

Yadav, Santosh Kumar. "Colouring of Graphs." In Advanced Graph Theory, 171–99. Cham: Springer International Publishing, 2023. http://dx.doi.org/10.1007/978-3-031-22562-8_6.

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

Yadav, Santosh Kumar. "Colouring of Graphs." In Discrete Mathematics with Graph Theory, 609–39. Cham: Springer International Publishing, 2023. http://dx.doi.org/10.1007/978-3-031-21321-2_15.

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

Lewis, R. M. R. "Introduction to Graph Colouring." In A Guide to Graph Colouring, 1–25. Cham: Springer International Publishing, 2015. http://dx.doi.org/10.1007/978-3-319-25730-3_1.

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

Lewis, R. M. R. "Introduction to Graph Colouring." In Texts in Computer Science, 1–16. Cham: Springer International Publishing, 2021. http://dx.doi.org/10.1007/978-3-030-81054-2_1.

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

Lewis, R. M. R. "Advanced Techniques for Graph Colouring." In A Guide to Graph Colouring, 55–77. Cham: Springer International Publishing, 2015. http://dx.doi.org/10.1007/978-3-319-25730-3_3.

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

Conference papers on the topic "Graph colouring"

1

Zatesko, Leandro M., Renato Carmo, and André L. P. Guedes. "Novel Procedures for Graph Edge-colouring." In XXXII Concurso de Teses e Dissertações da SBC. Sociedade Brasileira de Computação - SBC, 2019. http://dx.doi.org/10.5753/ctd.2019.6331.

Full text
Abstract:
We present a novel recolouring procedure for graph edge-colouring. We show that all graphs whose vertices have local degree sum not too large can be optimally edge-coloured in polynomial time. We also show that the set ofthe graphs satisfying this condition includes almost every graph (under the uniform distribution). We present further results on edge-colouring join graphs, chordal graphs, circular-arc graphs, and complementary prisms, whose proofs yield polynomial-time algorithms. Our results contribute towards settling the Over- full Conjecture, the main open conjecture on edge-colouring simple graphs. Fi- nally, we also present some results on total colouring.
APA, Harvard, Vancouver, ISO, and other styles
2

Karthikeyan, S., R. Suresh, and U. Mary. "Johan colouring and modified Johan colouring of line graph, middle graph of certain graphs." In INTELLIGENT BIOTECHNOLOGIES OF NATURAL AND SYNTHETIC BIOLOGICALLY ACTIVE SUBSTANCES: XIV Narochanskie Readings. AIP Publishing, 2023. http://dx.doi.org/10.1063/5.0178730.

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

Weffort-Santos, C. A., and L. L. C. Pedrosa. "(Star, k)-colourings of graphs with bounded treewidth." In Encontro de Teoria da Computação. Sociedade Brasileira de Computação - SBC, 2020. http://dx.doi.org/10.5753/etc.2020.11085.

Full text
Abstract:
We study a generalization of graph colouring define as follows. Given a graph G, a (star, k)-colouring of G is a colouring c : V(G) → {1, ..., k} such that every colour class induces a star. We propose an O*(2^(O(tw))k^(tw)-time algorithm that decides whether a graph G of treewidth at most tw admits a (star, k)-colouring. This resolves an open problem posed by Angelini et al. in 2017. Our approach can be extended to other defective colouring models.
APA, Harvard, Vancouver, ISO, and other styles
4

Silvoster, M. Leena. "Graph colouring based image similarity." In 2012 International Conference on Power, Signals, Controls and Computation (EPSCICON). IEEE, 2012. http://dx.doi.org/10.1109/epscicon.2012.6175260.

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

Hussin, Burairah, Abd Samad Hasan Basari, Abdul Samad Shibghatullah, Siti Azirah Asmai, and Norwahida Syazwani Othman. "Exam timetabling using graph colouring approach." In 2011 IEEE Conference on Open Systems (ICOS). IEEE, 2011. http://dx.doi.org/10.1109/icos.2011.6079274.

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

Zatesko, Leandro, Renato Carmo, and André Guedes. "Novel Procedures for Graph Edge-colouring." In ANAIS DO SIMPóSIO BRASILEIRO DE PESQUISA OPERACIONAL. Limeira - São Paulo, Brasil: Galoa, 2019. http://dx.doi.org/10.59254/sbpo-2019-107543.

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

Ben Hamida, Amira, Frédéric Le Mouël, Stéphane Frénot, and Mohamed Ben Ahmed. "Contextual service loading by dependency graph colouring." In the 8th international conference. New York, New York, USA: ACM Press, 2008. http://dx.doi.org/10.1145/1416729.1416758.

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

Ciardo, Lorenzo, and Stanislav Živný. "Approximate Graph Colouring and the Hollow Shadow." In STOC '23: 55th Annual ACM Symposium on Theory of Computing. New York, NY, USA: ACM, 2023. http://dx.doi.org/10.1145/3564246.3585112.

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

Annammal Arputhamary, I., and M. Helda Mercy. "Strong rainbow edge colouring and graph decomposition." In 2016 Online International Conference on Green Engineering and Technologies (IC-GET). IEEE, 2016. http://dx.doi.org/10.1109/get.2016.7916755.

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

Bernardi, João Pedro W., Sheila M. De Almeida, and Leandro M. Zatesko. "On Total and Edge-colouring of Proper Circular-arc Graphs." In III Encontro de Teoria da Computação. Sociedade Brasileira de Computação - SBC, 2018. http://dx.doi.org/10.5753/etc.2018.3557.

Full text
Abstract:
Deciding if a graph is Δ-edge-colourable (resp. (Δ + 1)-total colourable), although it is an NP-complete problem for graphs in general, is polynomially solvable for interval graphs of odd (resp. even) maximum degree Δ. An interesting superclass of the proper interval graphs are the proper circular-arc graphs, for which we suspect that Δ-edge-colourability is linear-time decidable. This work presents sufficient conditions for Δ-edge-colourability, (Δ + 1)-total colourability, and (Δ+2)-total colourability of proper circular-arc graphs. Our proofs are constructive and yield polynomial-time algorithms.
APA, Harvard, Vancouver, ISO, and other styles
You might also be interested in the extended bibliographies on the topic 'Graph colouring' 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