Randomly colouring graphs (a combinatorial view)
From MaRDI portal
Publication:458462
DOI10.1016/j.cosrev.2008.05.003zbMath1302.05060OpenAlexW1992301205MaRDI QIDQ458462
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
Random graphs (graph-theoretic aspects) (05C80) Research exposition (monographs, survey articles) pertaining to combinatorics (05-02) Coloring of graphs and hypergraphs (05C15)
Related Items
Cites Work
- List colouring when the chromatic number is close to the order of the graph
- Asymptotic behavior of the chromatic index for hypergraphs
- Induced matchings in bipartite graphs
- Graph labellings with variable weights, a survey
- Brick decompositions and the matching rank of graphs
- On a packing and covering problem
- Matching theory
- Near perfect coverings in graphs and hypergraphs
- Some intersection theorems for ordered sets and graphs
- Asymptotics of the chromatic index for multigraphs
- Proof of the van der Waerden conjecture regarding the permanent of a doubly stochastic matrix
- The solution of van der Waerden's problem for permanents
- Coloring nearly-disjoint hypergraphs with \(n + o(n)\) colors
- A still better performance guarantee for approximate graph coloring
- On an upper bound of the graph's chromatic number, depending on the graph's degree and density
- Inequalities in Fourier analysis
- Covering the vertex set of a graph with subgraphs of smaller degree
- 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
- A short proof of Minc's conjecture
- Chromatic number, girth and maximal degree
- On colorings of graphs without short cycles
- A short proof of the existence of highly chromatic hypergraphs without short cycles
- Zero knowledge and the chromatic number
- Boolean functions with low average sensitivity depend on few coordinates
- A bound on the total chromatic number
- Lower bounds on the competitive ratio for mobile user tracking and distributed job scheduling
- 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
- List edge and list total colourings of multigraphs
- The four-colour theorem
- Color-critical graphs on a fixed surface
- Counting 1-factors in regular bipartite graphs
- Coloring graphs with sparse neighborhoods
- Graph products, Fourier analysis and spectral techniques
- Planar graphs of maximum degree seven are Class I
- Boolean functions whose Fourier transform is concentrated on the first two levels.
- Asymptotically good list-colorings
- Concentration of measure and isoperimetric inequalities in product spaces
- Edge density and independence ratio in triangle-free graphs with maximum degree three
- On total colourings of graphs
- An upper bound for the total chromatic number
- Independent sets in graph powers are almost contained in juntas
- Perfect matchings in planar cubic graphs
- An upper bound for the chromatic number of line graphs
- Labeling planar graphs with a condition at distance two
- Improved bounds on acyclic edge colouring
- Fourier analysis and large independent sets in powers of complete graphs
- On the \(L(p,1)\)-labelling of graphs
- A survey on labeling graphs with a condition at distance two
- Étude des coefficients de Fourier des fonctions de \(L^ p(G)\)
- On the total coloring of certain graphs
- An Entropy Approach to the Hard-Core Model on Bipartite Graphs
- Acyclic edge colorings of graphs
- Entropy, independent sets and antichains: A new approach to Dedekind’s problem
- Hyperbolic polynomials approach to Van der Waerden/Schrijver-Valiant like conjectures
- The Fractional Chromatic Number of Graphs of Maximum Degree at Most Three
- Concentration for Independent Permutations
- Graph Theory and Probability
- On Moore Graphs with Diameters 2 and 3
- Coloring quasi-line graphs
- Total chromatic number of planar graphs with maximum degree ten
- List Colouring Squares of Planar Graphs
- Labelings of Graphs with Fixed and Variable Edge-Weights
- On two questions about circular choosability
- Hypergraphs, Entropy, and Inequalities
- A New Lower Bound on the Number of Perfect Matchings in Cubic Graphs
- Bounding χ in terms of ω and Δ for quasi-line graphs
- A Note On Reed's Conjecture
- Bounds for the Real Number Graph Labellings and Application to Labellings of the Triangular Lattice
- Total Colourings of Graphs
- On the total coloring of planar graphs.
- Star chromatic number
- Some Ramsey-Type Numbers and the Independence Ratio
- Rank of maximum matchings in a graph
- The NP-Completeness of Edge-Coloring
- Acyclic coloring of graphs
- An algorithmic approach to the Lovász local lemma. I
- Labelling Graphs with a Condition at Distance 2
- Applications of product colouring
- The Complexity of Near-Optimal Graph Coloring
- On the Shannon capacity of a graph
- Total Coloring With $\Delta + \mbox\lowercasepoly(\log \Delta)$ Colors
- On total 9-coloring planar graphs of maximum degree seven
- The Chromatic Number of Graph Powers
- Subgraphs with a large cochromatic number
- Total colorings of planar graphs with large maximum degree
- Free Bits, PCPs, and Nonapproximability---Towards Tight Results
- A Theorem about the Channel Assignment Problem
- Near-optimal list colorings
- The Theory of Information and Coding
- Circular choosability of graphs
- The acyclic edge chromatic number of a random d‐regular graph is d + 1
- Size and independence in triangle‐free graphs with maximum degree three
- An Improvement of Hind's Upper Bound on the Total Chromatic Number
- Coloring the square of a planar graph
- Nonrepetitive colorings of graphs
- On Brooks' Theorem for Sparse Graphs
- The $L(2,1)$-Labeling Problem on Graphs
- Source coding and graph entropies
- Colouring graphs when the number of colours is nearly the maximum degree
- Paths, Trees, and Flowers
- Multilevel Distance Labelings for Paths and Cycles
- On chromatic number of finite set-systems
- Concerning a Conjecture of Marshall Hall
- On Lower Bounds for Permanents of (0, 1) Matrices
- A Simplified Form for Nearly Reducible and Nearly Decomposable Matrices
- On Total Chromatic Number of a Graph
- On the Permanent of a Certain Class of (0, 1)-Matrices
- Upper bounds for permanents of $\left( {0,\,1} \right)$-matrices
- The Channel Assignment Problem with Variable Weights
- Some remarks on the theory of graphs
- A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations
- A Contribution to the Theory of Chromatic Polynomials
- Paths and Circuits in Critical Graphs
- Sur le coloriage des graphs
- Acyclic colorings of planar graphs
- 25 pretty graph colouring problems
- Circular chromatic number: A survey
- A new proof of the independence ratio of triangle-free cubic graphs
- An entropy proof of Bregman's theorem
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Randomly colouring graphs (a combinatorial view)
