Graph colouring and the probabilistic method
From MaRDI portal
Publication:5941810
zbMath0987.05002MaRDI QIDQ5941810
Bruce A. Reed, Michael S. O. Molloy
Publication date: 2 September 2001
Published in: Algorithms and Combinatorics (Search for Journal in Brave)
Research exposition (monographs, survey articles) pertaining to combinatorics (05-02) Combinatorial probability (60C05) Coloring of graphs and hypergraphs (05C15) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40)
Related Items
Colouring graphs with forbidden bipartite subgraphs, A new approach for determining fuzzy chromatic number of fuzzy graph, On Some Combinatorial Properties of Random Intersection Graphs, Brooks' Theorem and Beyond, A note on near-optimal coloring of shift hypergraphs, New bounds for Ryser’s conjecture and related problems, Submodular Functions: Learnability, Structure, and Optimization, Improper Choosability and Property B, On the Lovász Theta Function for Independent Sets in Sparse Graphs, On Verifying and Maintaining Connectivity of Interval Temporal Networks, EXPANDER GRAPHS AND SIEVING IN COMBINATORIAL STRUCTURES, A General Framework for Hypergraph Coloring, Counting colorings of triangle-free graphs, Weak degeneracy of graphs, Adaptable and conflict colouring multigraphs with no cycles of length three or four, A generalization of Faudree–Lehel conjecture holds almost surely for random graphs, Efficiently list‐edge coloring multigraphs asymptotically optimally, On the average size of independent sets in triangle-free graphs, Single‐conflict colouring, The list linear arboricity of graphs, Conflict‐free chromatic number versus conflict‐free chromatic index, Coloring bipartite graphs with semi-small list size, Occupancy fraction, fractional colouring, and triangle fraction, Asymptotically good edge correspondence colourings, Graph colorings with restricted bicolored subgraphs: I. Acyclic, star, and treewidth colorings, The Fractional Chromatic Number of \(\boldsymbol{K_{\Delta }}\)-Free Graphs, Graph and hypergraph colouring via nibble methods: a survey, The list version of the Borodin-Kostochka conjecture for graphs with large maximum degree, On the cop number of graphs of high girth, A proof of the Erdős-Faber-Lovász conjecture, Distributed algorithms, the Lovász local lemma, and descriptive combinatorics, Extremal bipartite independence number and balanced coloring, Multivariate spatio‐temporal modelling for assessing Antarctica's present‐day contribution to sea‐level rise, Borodin-Kostochka conjecture holds for odd-hole-free graphs, A note on the network coloring game: a randomized distributed \((\Delta+1)\)-coloring algorithm, On triangle-free list assignments, On Active and Passive Testing, 随机图的$f$-染色的分类 II, Existence of Spanning ℱ-Free Subgraphs with Large Minimum Degree, Highly Scalable Bayesian Geostatistical Modeling via Meshed Gaussian Processes on Partitioned Domains, Unnamed Item, A short proof of Bernoulli disjointness via the local lemma, Properly colored and rainbow copies of graphs with few cherries, On a conjecture about edge irregular total labelings, Linear Turán Numbers of Linear Cycles and Cycle-Complete Ramsey Numbers, A simplification of the difficult part of the Berge last conjecture, A simple dissertation around the Berge problem and the Hadwiger conjecture, Unnamed Item, Unnamed Item, A local epsilon version of Reed's conjecture, Local approximation of the maximum cut in regular graphs, Avoiding Multiple Repetitions in Euclidean Spaces, Packing Graphs of Bounded Codegree, Analysis of Sparse Cutting Planes for Sparse MILPs with Applications to Stochastic MILPs, Distributed algorithms for the Lovász local lemma and graph coloring, Counting Independent Sets in Hypergraphs, Coloring Graphs with Dense Neighborhoods, Recent progress on strong edge-coloring of graphs, An Introduction to Temporal Graphs: An Algorithmic Perspective*, Unnamed Item, Fractional Chromatic Number, Maximum Degree, and Girth, Phase Transitions for Random Geometric Preferential Attachment Graphs, Percolation on Random Graphs with a Fixed Degree Sequence, $t$-Strong Cliques and the Degree-Diameter Problem, Clique number of the square of a line graph, Improved upper bound for generalized acyclic chromatic number of graphs, Improved bounds on the generalized acyclic chromatic number, Acyclic coloring of graphs with some girth restriction, Traveling salesman problems in temporal graphs, On decomposing graphs of large minimum degree into locally irregular subgraphs, Colouring graphs with sparse neighbourhoods: bounds and applications, Majority colourings of digraphs, The asymptotic behavior of the correspondence chromatic number, Asymptotically optimal neighbor sum distinguishing total colorings of graphs, Distant set distinguishing total colourings of graphs, The list chromatic number of graphs with small clique number, Dynamic \(F\)-free coloring of graphs, Stack domination density, Colouring Non-sparse Random Intersection Graphs, Randomly coloring planar graphs with fewer colors than the maximum degree, Asymptotically optimal neighbour sum distinguishing colourings of graphs, Independent transversals in locally sparse graphs, An Introduction to Temporal Graphs: An Algorithmic Perspective, Extension from precoloured sets of edges, Graph coloring and semidefinite rank, Graph factors and factorization: 1985--2003: a survey, Sets that are connected in two random graphs, Uniquely \(D\)-colourable digraphs with large girth. II: Simplification via generalization, Bounding \(\chi\) by a fraction of \(\Delta\) for graphs without large cliques, On the standard \((2,2)\)-conjecture, Domination and fractional domination in digraphs, Pattern avoidance on graphs, The complexity of optimal design of temporally connected graphs, Almost color-balanced perfect matchings in color-balanced complete graphs, Distant irregularity strength of graphs with bounded minimum degree, Equipartite polytopes, An average degree condition for independent transversals, Colouring square-free graphs without long induced paths., Disjoint cycles of different lengths in graphs and digraphs, Random walks on quasirandom graphs, Distant set distinguishing edge colourings of graphs, Improved upper bounds on acyclic edge colorings, Long directed rainbow cycles and rainbow spanning trees, Packing two graphs of even girth 10, \(k\)-cut on paths and some trees, 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, Stochastic coalescence in logarithmic time, Some defective parameters in graphs, Partition and disjoint cycles in digraphs, Equivariant maps to subshifts whose points have small stabilizers, Frugal, acyclic and star colourings of graphs, A unified approach to distance-two colouring of graphs on surfaces, On the adjacent vertex-distinguishing acyclic edge coloring of some graphs, Colouring graphs when the number of colours is almost the maximum degree, 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, Total edge irregularity strength of large graphs, Embedding Graphs into Larger Graphs: Results, Methods, and Problems, Degenerate and star colorings of graphs on surfaces, Polynomial \(\chi \)-binding functions and forbidden induced subgraphs: a survey, A note on the discrepancy of matrices with bounded row and column sums, A superlocal version of Reed's conjecture, Thue type problems for graphs, points, and numbers, Improved bounds on acyclic edge colouring, Temporal network optimization subject to connectivity constraints, The classification of \(f\)-coloring of graphs with large maximum degree, Improved distributed \(\Delta\)-coloring, \((p,1)\)-total labelling of graphs, Bounds on the average and minimum attendance in preference-based activity scheduling, A proof of the Barát-Thomassen conjecture, How to determine if a random graph with a fixed degree sequence has a giant component, On splitting digraphs, Scaling laws for maximum coloring of random geometric graphs, On the chromatic number of non-sparse random intersection graphs, On the \(L(p,1)\)-labelling of graphs, Fractional strong chromatic index of bipartite graphs, Acyclic improper colourings of graphs with bounded maximum degree, Fractional \(L\)-intersecting families, Backbone colorings of graphs with bounded degree, Maximal operators and differentiation theorems for sparse sets, Hamiltonian cycles in Dirac graphs, Temporal matching, Equipartite graphs, Large Independent Sets in Subquartic Planar Graphs, Consistent structure estimation of exponential-family random graph models with block structure, Coloring Sparse Hypergraphs, Ergodic theorems for the shift action and pointwise versions of the Abért-Weiss theorem, Very fast construction of bounded‐degree spanning graphs via the semi‐random graph process, Coloring Powers and Girth, Measurable versions of the Lovász local lemma and measurable graph colorings, An upper bound for the adjacent vertex distinguishing acyclic edge chromatic number of a graph, Colouring square-free graphs without long induced paths, Edge irregular total labellings for graphs of linear size, Randomized algorithms for stabilizing switching signals, Concentration for self-bounding functions and an inequality of Talagrand, Some Results on Chromatic Number as a Function of Triangle Count, \(\Delta+300\) is a bound on the adjacent vertex distinguishing edge chromatic number, A note on coloring vertex-transitive graphs, On the coequal values of total chromatic number and chromatic index, An ensemble of high rank matrices arising from tournaments, \((\mathcal{P},\mathcal{Q})\)-total \((r,s)\)-colorings of graphs, On decomposing regular graphs into locally irregular subgraphs
