Graph colouring and the probabilistic method
This monograph provides an accessible and unified treatment of major advances made in graph colouring via the probabilistic method. It is divided into twenty-five chapters. The first two of them are devoted the basic notions of graph colouring and probability theory. Chapters 3-5 present the first moment method, the celebrated Lovász local lemma and the Chernoff bound. These form fundamental tools of the probabilistic method and are used throughout this book. Chapters 6-25 cover the following topics: Hadwiger's conjecture, A first glimpse of total colouring, The strong chromatic number, Total colouring revisited, Talagrand's inequality and colouring sparse graphs, Azuma's inequality and a strengthening of Brooks' theorem, Graphs with girth at least five, Triangle-free graphs, The list colouring conjecture, The structural decomposition, \(\omega\), \(\Delta\) and \(\chi\), Near optimal total colouring: Sparse graphs and general graphs, Generalizations of the local lemma, Finding fractional colourings and large stable sets, Hard-core distributions on matchings, The asymptotics of edge colouring multigraphs, The method of conditional expectations, Algorithmic aspects of the local lemma. Many exercises and excellent remarks are presented and discussed. Also very useful is the list of up-to-date references for current research. This monograph will be useful both to researches and graduate students in graph theory, discrete mathematics, theoretical computer science and probability.
- Equipartite graphs
- An upper bound for the adjacent vertex distinguishing acyclic edge chromatic number of a graph
- Edge irregular total labellings for graphs of linear size
- Probabilistic methods in coloring and decomposition problems
- Improved upper bound for generalized acyclic chromatic number of graphs
- The list chromatic number of graphs with small clique number
- Dynamic \(F\)-free coloring of graphs
- Extension from precoloured sets of edges
- Domination and fractional domination in digraphs
- Disjoint cycles of different lengths in graphs and digraphs
- Distant set distinguishing edge colourings of graphs
- Packing two graphs of even girth 10
- Polynomial \(\chi \)-binding functions and forbidden induced subgraphs: a survey
- Temporal network optimization subject to connectivity constraints
- The classification of \(f\)-coloring of graphs with large maximum degree
- On splitting digraphs
- Stochastic coalescence in logarithmic time
- Some defective parameters in graphs
- Improved distributed \(\Delta\)-coloring
- A proof of the Barát-Thomassen conjecture
- Fractional L-intersecting families
- On the coequal values of total chromatic number and chromatic index
- An ensemble of high rank matrices arising from tournaments
- Colouring graphs with sparse neighbourhoods: bounds and applications
- Graph coloring and semidefinite rank
- Bounding \(\chi\) by a fraction of \(\Delta\) for graphs without large cliques
- Long directed rainbow cycles and rainbow spanning trees
- Bounds on the average and minimum attendance in preference-based activity scheduling
- Temporal matching
- Consistent structure estimation of exponential-family random graph models with block structure
- Ergodic theorems for the shift action and pointwise versions of the Abért-Weiss theorem
- Measurable versions of the Lovász local lemma and measurable graph colorings
- Colouring square-free graphs without long induced paths
- Randomized algorithms for stabilizing switching signals
- A note on coloring vertex-transitive graphs
- \((\mathcal{P},\mathcal{Q})\)-total \((r,s)\)-colorings of graphs
- On decomposing regular graphs into locally irregular subgraphs
- Asymptotically optimal neighbor sum distinguishing total colorings of graphs
- Independent transversals in locally sparse graphs
- The complexity of optimal design of temporally connected graphs
- Distant irregularity strength of graphs with bounded minimum degree
- \(k\)-cut on paths and some trees
- A unified approach to distance-two colouring of graphs on surfaces
- Improved bounds on acyclic edge colouring
- \((p,1)\)-total labelling of graphs
- On the \(L(p,1)\)-labelling of graphs
- An exact method for graph coloring
- \(\Delta+300\) is a bound on the adjacent vertex distinguishing edge chromatic number
- Majority colourings of digraphs
- The asymptotic behavior of the correspondence chromatic number
- Distant set distinguishing total colourings of graphs
- Stack domination density
- Uniquely \(D\)-colourable digraphs with large girth. II: Simplification via generalization
- On the standard (2,2)-conjecture
- Almost color-balanced perfect matchings in color-balanced complete graphs
- An average degree condition for independent transversals
- Cooperative colorings of forests
- Majority edge-colorings of graphs
- Mini-workshop: Descriptive combinatorics, LOCAL algorithms and random processes. Abstracts from the mini-workshop held February 13--19, 2022
- Partition and disjoint cycles in digraphs
- Equivariant maps to subshifts whose points have small stabilizers
- Clique number of the square of a line graph
- Improved bounds on the generalized acyclic chromatic number
- Large independent sets in subquartic planar graphs
- Coloring sparse hypergraphs
- Acyclic coloring of graphs with some girth restriction
- Coloring powers and girth
- Traveling salesman problems in temporal graphs
- On decomposing graphs of large minimum degree into locally irregular subgraphs
- Sets that are connected in two random graphs
- Some results on chromatic number as a function of triangle count
- Colouring Non-sparse Random Intersection Graphs
- Embedding Graphs into Larger Graphs: Results, Methods, and Problems
- Colouring square-free graphs without long induced paths
- Very fast construction of bounded‐degree spanning graphs via the semi‐random graph process
- Concentration for self-bounding functions and an inequality of Talagrand
- Asymptotically optimal neighbour sum distinguishing colourings of graphs
- An introduction to temporal graphs: an algorithmic perspective
- On Some Combinatorial Properties of Random Intersection Graphs
- Brooks' Theorem and Beyond
- A note on near-optimal coloring of shift hypergraphs
- The Randomized Coloring Procedure with Symmetry-Breaking
- A simplification of the difficult part of the Berge last conjecture
- A simple dissertation around the Berge problem and the Hadwiger conjecture
- Random walks on quasirandom graphs
- Improved upper bounds on acyclic edge colorings
- scientific article; zbMATH DE number 1303525 (Why is no real title available?)
- On the adjacent vertex-distinguishing acyclic edge coloring of some graphs
- Submodular functions: learnability, structure, and optimization
- On the Lovász Theta Function for Independent Sets in Sparse Graphs
- Expander graphs and sieving in combinatorial structures
- On the average size of independent sets in triangle-free graphs
- Colouring graphs when the number of colours is almost the maximum degree
- Linear Turán Numbers of Linear Cycles and Cycle-Complete Ramsey Numbers
- Coloring a graph with \(\Delta-1\) colors: conjectures equivalent to the Borodin-Kostochka conjecture that appear weaker
- Decomposition of bounded degree graphs into \(C_4\)-free subgraphs
- A note on the discrepancy of matrices with bounded row and column sums
- A superlocal version of Reed's conjecture
- Packing graphs of bounded codegree
- Fractional chromatic number, maximum degree, and girth
This page was built for publication: Graph colouring and the probabilistic method
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5941810)
