Relevant bibliographies by topics / List colouring

Contents

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

Academic literature on the topic 'List colouring'

Author: Grafiati
Published: 4 June 2021
Last updated: 18 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 'List 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 "List colouring"

1

Reed, Bruce. "The list colouring constants." Journal of Graph Theory 31, no. 2 (1999): 149–53. http://dx.doi.org/10.1002/(sici)1097-0118(199906)31:2<149::aid-jgt8>3.0.co;2-#.

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

Bu, Yuehua, Stephen Finbow, Daphne Der-Fen Liu, and Xuding Zhu. "List backbone colouring of graphs." Discrete Applied Mathematics 167 (April 2014): 45–51. http://dx.doi.org/10.1016/j.dam.2013.11.008.

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

Havet, Frédéric, Jan van den Heuvel, Colin McDiarmid, and Bruce Reed. "List Colouring Squares of Planar Graphs." Electronic Notes in Discrete Mathematics 29 (August 2007): 515–19. http://dx.doi.org/10.1016/j.endm.2007.07.079.

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

HAXELL, P. E. "A Note on Vertex List Colouring." Combinatorics, Probability and Computing 10, no. 4 (2001): 345–47. http://dx.doi.org/10.1017/s0963548301004758.

Full text
Abstract:
Let k be a positive integer and let G be a graph. Suppose a list S(v) of positive integers is assigned to each vertex v, such that(1) [mid ]S(v)[mid ] = 2k for each vertex v of G, and(2) for each vertex v, and each c ∈ S(v), the number of neighbours w of v for which c ∈ S(w) is at most k.Then we prove that there exists a proper vertex colouring f of G such that f(v) ∈ S(v) for each v ∈ V(G). This proves a weak version of a conjecture of Reed.
APA, Harvard, Vancouver, ISO, and other styles
5

SUBRAMANIAN, C. R. "List Set Colouring: Bounds and Algorithms." Combinatorics, Probability and Computing 16, no. 01 (2006): 145. http://dx.doi.org/10.1017/s0963548306007735.

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

Zhu, Xuding. "Multiple list colouring of planar graphs." Journal of Combinatorial Theory, Series B 122 (January 2017): 794–99. http://dx.doi.org/10.1016/j.jctb.2016.09.008.

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

Qi, Hao. "Bounds on partial online list colouring." Information Processing Letters 127 (November 2017): 23–26. http://dx.doi.org/10.1016/j.ipl.2017.06.009.

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

šKREKOVSKI, R. "A Grötzsch-Type Theorem for List Colourings with Impropriety One." Combinatorics, Probability and Computing 8, no. 5 (1999): 493–507. http://dx.doi.org/10.1017/s096354839900396x.

Full text
Abstract:
A graph G is m-choosable with impropriety d, or simply (m, d)*-choosable, if, for every list assignment L, where [mid ]L(v)[mid ][ges ]m for every v∈V(G), there exists an L-colouring of G such that each vertex of G has at most d neighbours coloured with the same colour as itself. We prove a Grötzsch-type theorem for list colourings with impropriety one, that is, the (3, 1)*-choosability for triangle-free planar graphs; in the proof the method of extending a precolouring of a 4- or 5-cycle is used.
APA, Harvard, Vancouver, ISO, and other styles
9

šKREKOVSKI, R. "List Improper Colourings of Planar Graphs." Combinatorics, Probability and Computing 8, no. 3 (1999): 293–99. http://dx.doi.org/10.1017/s0963548399003752.

Full text
Abstract:
A graph G is m-choosable with impropriety d, or simply (m, d)*-choosable, if for every list assignment L, where [mid ]L(v)[mid ][ges ]m for every v∈V(G), there exists an L-colouring of G such that each vertex of G has at most d neighbours coloured with the same colour as itself. We show that every planar graph is (3, 2)*-choosable and every outerplanar graph is (2, 2)*-choosable. We also propose some interesting problems about this colouring.
APA, Harvard, Vancouver, ISO, and other styles
10

Amini, Omid, and Bruce Reed. "List Colouring Constants of Triangle Free Graphs." Electronic Notes in Discrete Mathematics 30 (February 2008): 135–40. http://dx.doi.org/10.1016/j.endm.2008.01.024.

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

Dissertations / Theses on the topic "List colouring"

1

Hetherington, Timothy J. "List-colourings of near-outerplanar graphs." Thesis, Nottingham Trent University, 2007. http://irep.ntu.ac.uk:80/R/?func=dbin-jump-full&object_id=195759.

Full text
Abstract:
A list-colouring of a graph is an assignment of a colour to each vertex v from its own list L(v) of colours. Instead of colouring vertices we may want to colour other elements of a graph such as edges, faces, or any combination of vertices, edges and faces. In this thesis we will study several of these different types of list-colouring, each for the class of a near-outerplanar graphs. Since a graph is outerplanar if it is both K4-minor-free and K2,3-minor-free, then by a near-outerplanar graph we mean a graph that is either K4-minor-free or K2,3-minor-free. Chapter 1 gives an introduction to the area of graph colourings, and includes a review of several results and conjectures in this area. In particular, four important and interesting conjectures in graph theory are the List-Edge-Colouring Conjecture (LECC), the List-Total-Colouring Conjecture (LTCC), the Entire Colouring Conjecture (ECC), and the List-Square-Colouring Conjecture (LSCC), each of which will be discussed in Chapter 1. In Chapter 2 we include a proof of the LECC and LTCC for all near-outerplanar graphs. In Chapter 3 we will study the list-colouring of a near-outerplanar graph in which vertices and faces, edges and faces, or vertices, edges and face are to be coloured. The results for the case when all elements are to be coloured will prove the ECC for all near-outerplanar graphs. In Chapter 4 we will study the list-colouring of the square of a K4-minor-free graph, and in Chapter 5 we will study the list-colouring of the square of a K2,3-minor-free graph. In Chapter 5 we include a proof of the LSCC for all K2,3-minor-free graphs with maximum degree at least six.
APA, Harvard, Vancouver, ISO, and other styles
2

Waller, Adrian Owen. "Some types of list colourings of graphs." Thesis, Royal Holloway, University of London, 1996. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.363046.

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

Yang, Chung-Ying, and 楊宗穎. "Colouring, circular list colouring and adapted game colouring of graphs." Thesis, 2010. http://ndltd.ncl.edu.tw/handle/264n52.

Full text
Abstract:
博士<br>國立中山大學<br>應用數學系研究所<br>98<br>This thesis discusses colouring, circular list colouring and adapted game colouring of graphs. For colouring, this thesis obtains a sufficient condition for a planar graph to be 3-colourable. Suppose G is a planar graph. Let H_G be the graph with vertex set V (H_G) = {C : C is a cycle of G with |C| ∈ {4, 6, 7}} and edge set E(H_G) = {CiCj : Ci and Cj have edges in common}. We prove that if any 3-cycles and 5-cycles are not adjacent to i-cycles for 3 ≤ i ≤ 7, and H_G is a forest, then G is 3-colourable. For circular consecutive choosability, this thesis obtains a basic relation among chcc(G), X(G) and Xc(G) for any finite graph G. We show that for any finite graph G, X(G) − 1 ≤ chcc(G) &amp;lt; 2 Xc(G). We also determine the value of chcc(G) for complete graphs, trees, cycles, balanced complete bipartite graphs and some complete multi-partite graphs. Upper and lower bounds for chcc(G) are given for some other classes of graphs. For adapted game chromatic number, this thesis studies the adapted game chromatic number of various classes of graphs. We prove that the maximum adapted game chromatic number of trees is 3; the maximum adapted game chromatic number of outerplanar graphs is 5; the maximum adapted game chromatic number of partial k-trees is between k + 2 and 2k + 1; and the maximum adapted game chromatic number of planar graphs is between 6 and 11. We also give upper bounds for the Cartesian product of special classes of graphs, such as the Cartesian product of partial k-trees and outerplanar graphs, or planar graphs.
APA, Harvard, Vancouver, ISO, and other styles
4

Pei, Martin. "List colouring hypergraphs and extremal results for acyclic graphs." Thesis, 2008. http://hdl.handle.net/10012/3715.

Full text
Abstract:
We study several extremal problems in graphs and hypergraphs. The first one is on list-colouring hypergraphs, which is a generalization of the ordinary colouring of hypergraphs. We discuss two methods for determining the list-chromatic number of hypergraphs. One method uses hypergraph polynomials, which invokes Alon's combinatorial nullstellensatz. This method usually requires computer power to complete the calculations needed for even a modest-sized hypergraph. The other method is elementary, and uses the idea of minimum improper colourings. We apply these methods to various classes of hypergraphs, including the projective planes. We focus on solving the list-colouring problem for Steiner triple systems (STS). It is not hard using either method to determine that Steiner triple systems of orders 7, 9 and 13 are 3-list-chromatic. For systems of order 15, we show that they are 4-list-colourable, but they are also ``almost'' 3-list-colourable. For all Steiner triple systems, we prove a couple of simple upper bounds on their list-chromatic numbers. Also, unlike ordinary colouring where a 3-chromatic STS exists for each admissible order, we prove using probabilistic methods that for every $s$, every STS of high enough order is not $s$-list-colourable. The second problem is on embedding nearly-spanning bounded-degree trees in sparse graphs. We determine sufficient conditions based on expansion properties for a sparse graph to embed every nearly-spanning tree of bounded degree. We then apply this to random graphs, addressing a question of Alon, Krivelevich and Sudakov, and determine a probability $p$ where the random graph $G_{n,p}$ asymptotically almost surely contains every tree of bounded degree. This $p$ is nearly optimal in terms of the maximum degree of the trees that we embed. Finally, we solve a problem that arises from quantum computing, which can be formulated as an extremal question about maximizing the size of a type of acyclic directed graph.
APA, Harvard, Vancouver, ISO, and other styles
5

Bird, William Herbert. "Graph Distinguishability and the Generation of Non-Isomorphic Labellings." Thesis, 2013. http://hdl.handle.net/1828/4839.

Full text
Abstract:
A distinguishing colouring of a graph G is a labelling of the vertices of G with colours such that no non-trivial automorphism of G preserves all colours. The distinguishing number of G is the minimum number of colours in a distinguishing colouring. This thesis presents a survey of the history of distinguishing colouring problems and proves new bounds and computational results about distinguishability. An algorithm to generate all labellings of a graph up to isomorphism is presented and compared to a previously published algorithm. The new algorithm is shown to have performance competitive with the existing algorithm, as well as being able to process automorphism groups far larger than the previous limit. A specialization of the algorithm is used to generate all minimal distinguishing colourings of a set of graphs with large automorphism groups and compute their distinguishing numbers.<br>Graduate<br>0984<br>0405<br>bbird@uvic.ca
APA, Harvard, Vancouver, ISO, and other styles

Book chapters on the topic "List colouring"

1

Derka, Martin, Alejandro López-Ortiz, and Daniela Maftuleac. "List Colouring and Partial List Colouring of Graphs On-line." In Lecture Notes in Computer Science. Springer International Publishing, 2016. http://dx.doi.org/10.1007/978-3-319-29516-9_11.

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

Molloy, Michael, and Bruce Reed. "The List Colouring Conjecture." In Algorithms and Combinatorics. Springer Berlin Heidelberg, 2002. http://dx.doi.org/10.1007/978-3-642-04016-0_14.

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

Cogis, Olivier, Jean-Claude König, and Jérôme Palaysi. "On the List Colouring Problem." In Advances in Computing Science — ASIAN 2002. Springer Berlin Heidelberg, 2002. http://dx.doi.org/10.1007/3-540-36184-7_6.

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

Sali, Attila, and Gábor Simonyi. "Oriented list colouring of undirected graphs." In Contemporary Trends in Discrete Mathematics. American Mathematical Society, 1999. http://dx.doi.org/10.1090/dimacs/049/22.

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

Frieze, Alan, Dieter Mitsche, Xavier Pérez-Giménez, and Paweł Prałat. "On-Line List Colouring of Random Graphs." In Trends in Mathematics. Springer International Publishing, 2017. http://dx.doi.org/10.1007/978-3-319-51753-7_8.

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

Gravin, Nick. "Time Optimal d-List Colouring of a Graph." In Computer Science – Theory and Applications. Springer Berlin Heidelberg, 2010. http://dx.doi.org/10.1007/978-3-642-13182-0_15.

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

Khandelwal, Aditi, Pallavi Jain, and Gur Saran. "List Colouring of Graphs Using a Genetic Algorithm." In Smart Computing and Informatics. Springer Singapore, 2017. http://dx.doi.org/10.1007/978-981-10-5544-7_56.

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

Bagneris, Mia L. "List of figures." In Colouring the Caribbean. Manchester University Press, 2017. http://dx.doi.org/10.7765/9781526120465.00003.

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

Bollobás, B., and H. R. Hind. "A New Upper Bound for the List Chromatic Number." In Graph Colouring and Variations. Elsevier, 1989. http://dx.doi.org/10.1016/s0167-5060(08)70299-1.

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

Woodall, D. R. "List colourings of graphs." In Surveys in Combinatorics, 2001. Cambridge University Press, 2001. http://dx.doi.org/10.1017/cbo9780511721328.012.

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

Conference papers on the topic "List colouring"

1

Egri, László, Pavol Hell, Benoit Larose, and Arash Rafiey. "Space complexity of list H-colouring: a dichotomy." In Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics, 2013. http://dx.doi.org/10.1137/1.9781611973402.26.

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

Cygan, Marek, Marcin Pilipczuk, Michal Pilipczuk, and Jakub Onufry Wojtaszczyk. "The stubborn problem is stubborn no more (a polynomial algorithm for 3–compatible colouring and the stubborn list partition problem)." In Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics, 2011. http://dx.doi.org/10.1137/1.9781611973082.128.

Full text
APA, Harvard, Vancouver, ISO, and other styles
You might also be interested in the extended bibliographies on the topic 'List colouring' for particular source types:
Journal articles
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