Randomly colouring graphs (a combinatorial view)

DOI10.1016/J.COSREV.2008.05.003zbMATH Open1302.05060OpenAlexW1992301205MaRDI QIDQ458462FDOQ458462

Authors: Jean-Sébastien Sereni 

Publication date: 7 October 2014

Published in: Computer Science Review (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.cosrev.2008.05.003

Recommendations

• Colouring random graphs
• scientific article; zbMATH DE number 4101221
• scientific article
• scientific article; zbMATH DE number 1984543
• Randomly coloring random graphs
• Coloring random graphs
• Coloring random graphs
• Coloring random graphs
• Colouring Random Regular Graphs
• Randomly colorable graphs in greedy coloring

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Research exposition (monographs, survey articles) pertaining to combinatorics (05-02) Coloring of graphs and hypergraphs (05C15)

Cites Work

• Multilevel Distance Labelings for Paths and Cycles
• Title not available (Why is that?)
• Title not available (Why is that?)
• The Theory of Information and Coding
• A short proof of Minc's conjecture
• On the \(L(p,1)\)-labelling of graphs
• Entropy, independent sets and antichains: A new approach to Dedekind's problem
• A Theorem about the Channel Assignment Problem
• Brick decompositions and the matching rank of graphs
• Rank of maximum matchings in a graph
• Chromatic number, girth and maximal degree
• A short proof of the existence of highly chromatic hypergraphs without short cycles
• List Colouring Squares of Planar Graphs
• Title not available (Why is that?)
• The Complexity of Near-Optimal Graph Coloring
• The Channel Assignment Problem with Variable Weights
• Graph labellings with variable weights, a survey
• Some Ramsey-Type Numbers and the Independence Ratio
• A new proof of the independence ratio of triangle-free cubic graphs
• Perfect matchings in planar cubic graphs
• Coloring quasi-line graphs
• A new lower bound on the number of perfect matchings in cubic graphs
• Bounding χ in terms of ω and Δ for quasi-line graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Colouring graphs when the number of colours is nearly the maximum degree
• Title not available (Why is that?)
• The acyclic edge chromatic number of a random d‐regular graph is d + 1
• Free Bits, PCPs, and Nonapproximability---Towards Tight Results
• A bound on the total chromatic number
• Coloring nearly-disjoint hypergraphs with \(n + o(n)\) colors
• The solution of van der Waerden's problem for permanents
• A still better performance guarantee for approximate graph coloring
• Covering the vertex set of a graph with subgraphs of smaller degree
• On colorings of graphs without short cycles
• Lower bounds on the competitive ratio for mobile user tracking and distributed job scheduling
• Graph products, Fourier analysis and spectral techniques
• Boolean functions whose Fourier transform is concentrated on the first two levels.
• Asymptotically good list-colorings
• Edge density and independence ratio in triangle-free graphs with maximum degree three
• An upper bound for the total chromatic number
• Labeling planar graphs with a condition at distance two
• Fourier analysis and large independent sets in powers of complete graphs
• Perfect graphs and graph entropy: An updated survey
• Title not available (Why is that?)
• Hyperbolic polynomials approach to Van der Waerden/Schrijver-Valiant like conjectures
• The fractional chromatic number of graphs of maximum degree at most three
• Title not available (Why is that?)
• Labelings of Graphs with Fixed and Variable Edge-Weights
• On two questions about circular choosability
• Title not available (Why is that?)
• Bounds for the Real Number Graph Labellings and Application to Labellings of the Triangular Lattice
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Total Coloring With $\Delta + \mbox\lowercasepoly(\log \Delta)$ Colors
• Subgraphs with a large cochromatic number
• Near-optimal list colorings
• Circular choosability of graphs
• An Improvement of Hind's Upper Bound on the Total Chromatic Number
• Title not available (Why is that?)
• Title not available (Why is that?)
• Source coding and graph entropies
• Title not available (Why is that?)
• Concerning a Conjecture of Marshall Hall
• On Lower Bounds for Permanents of (0, 1) Matrices
• On the Permanent of a Certain Class of (0, 1)-Matrices
• Title not available (Why is that?)
• Paths and Circuits in Critical Graphs
• Probability and random processes.
• A Contribution to the Theory of Chromatic Polynomials
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Matching theory
• A Simplified Form for Nearly Reducible and Nearly Decomposable Matrices
• On an upper bound of the graph's chromatic number, depending on the graph's degree and density
• Graph Theory and Probability
• On the Shannon capacity of a graph
• Paths, Trees, and Flowers
• Sur le coloriage des graphs
• On a packing and covering problem
• Inequalities in Fourier analysis
• A bound on the chromatic number of a graph
• Every planar map is four colorable. I: Discharging
• Every planar map is four colorable. II: Reducibility
• List edge and list total colourings of multigraphs
• Random graphs.
• The probabilistic method. With an appendix on the life and work of Paul Erdős.
• Title not available (Why is that?)
• The NP-Completeness of Edge-Coloring
• Title not available (Why is that?)
• Size and independence in triangle‐free graphs with maximum degree three
• On Brooks' Theorem for Sparse Graphs
• Title not available (Why is that?)
• Some remarks on the theory of graphs
• Acyclic colorings of planar graphs
• Near perfect coverings in graphs and hypergraphs
• Some intersection theorems for ordered sets and graphs
• Boolean functions with low average sensitivity depend on few coordinates
• Relating path coverings to vertex labellings with a condition at distance two
• A bound on the strong chromatic index of a graph
• The total chromatic number of any multigraph with maximum degree five is at most seven
• The four-colour theorem
• Color-critical graphs on a fixed surface
• Concentration of measure and isoperimetric inequalities in product spaces
• On total colourings of graphs
• Independent sets in graph powers are almost contained in juntas
• Improved bounds on acyclic edge colouring
• On the total coloring of certain graphs
• An entropy approach to the hard-core model on bipartite graphs
• Acyclic edge colorings of graphs
• Total chromatic number of planar graphs with maximum degree ten
• Hypergraphs, entropy, and inequalities
• Total Colourings of Graphs
• On the total coloring of planar graphs.
• Acyclic coloring of graphs
• Labelling Graphs with a Condition at Distance 2
• Applications of product colouring
• On total 9-coloring planar graphs of maximum degree seven
• Title not available (Why is that?)
• Total colorings of planar graphs with large maximum degree
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• List colouring when the chromatic number is close to the order of the graph
• On Total Chromatic Number of a Graph
• Title not available (Why is that?)
• A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations
• An entropy proof of Bregman's theorem
• Asymptotic behavior of the chromatic index for hypergraphs
• Induced matchings in bipartite graphs
• An upper bound for the chromatic number of line graphs
• A survey on labeling graphs with a condition at distance two
• On Moore Graphs with Diameters 2 and 3
• A Note On Reed's Conjecture
• Title not available (Why is that?)
• Title not available (Why is that?)
• 25 pretty graph colouring problems
• An algorithmic approach to the Lovász local lemma. I
• Title not available (Why is that?)
• Asymptotics of the chromatic index for multigraphs
• Planar graphs of maximum degree seven are Class I
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Nonrepetitive colorings of graphs
• Title not available (Why is that?)
• Upper bounds for permanents of $\left( {0,\,1} \right)$-matrices
• Étude des coefficients de Fourier des fonctions de \(L^ p(G)\)
• Star chromatic number
• Title not available (Why is that?)
• Title not available (Why is that?)
• Coloring the square of a planar graph
• The $L(2,1)$-Labeling Problem on Graphs
• Circular chromatic number: A survey
• Title not available (Why is that?)
• On chromatic number of finite set-systems
• Title not available (Why is that?)
• Proof of the van der Waerden conjecture regarding the permanent of a doubly stochastic matrix
• Zero knowledge and the chromatic number
• Counting 1-factors in regular bipartite graphs
• Coloring graphs with sparse neighborhoods
• Concentration for Independent Permutations
• The Chromatic Number of Graph Powers
• Title not available (Why is that?)

Cited In (13)

• Graph colouring and the probabilistic method
• Random coloring evolution on graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Coloring random graphs
• Coloring random graphs
• Finding Pseudorandom Colorings of Pseudorandom Graphs
• Colouring Random 4-Regular Graphs
• Combinatorial optimization in system configuration design
• Randomized Δ-edge colouring via exchanges of complex colours
• Randomly coloring random graphs
• Title not available (Why is that?)
• Colouring Random Regular Graphs

This page was built for publication: Randomly colouring graphs (a combinatorial view)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q458462)