Colouring a graph frugally
From MaRDI portal
Every graph with maximum degree \(\Delta\geq\Delta_0\) has a proper \((\Delta+1)\)-coloring in which every color class has at most \(\log^8\Delta\) elements in the neighborhood of any vertex. If \(\beta\geq 1\) and the maximum degree is \(\delta\geq\Delta_\beta\) then there is a \(\max((\beta+1)\Delta,e^3\Delta^{1+{1\over\beta}})\)-coloring in which every color class has at most \(\beta\) elements in the neighborhood of any vertex. An example of Noga Alon gives that this is essentially best possible.
Recommendations
Cites work
Cited in
(42)- Graph coloring with cardinality constraints on the neighborhoods
- Linear coloring of planar graphs with large girth
- Coloring graphs with sparse neighborhoods
- Linear coloring of graphs
- New upper bounds on linear coloring of planar graphs
- The linear \(t\)-colorings of Sierpiński-like graphs
- The complexity of frugal colouring
- Intersection dimension and graph invariants
- Dynamic proper colorings of a graph
- Linear choosability of sparse graphs
- The \((d, 1)\)-total labelling of Sierpiński-like graphs
- Linear colorings of subcubic graphs
- Bounds on vertex colorings with restrictions on the union of color classes
- Nondegenerate colourings in the Brooks theorem
- Linear coloring of planar graphs without 4-cycles
- Conflict-free colourings of graphs and hypergraphs
- On linear coloring of planar graphs with small girth
- Improved bounds on coloring of graphs
- Locally identifying colourings for graphs with given maximum degree
- Coloring nonuniform hypergraphs: A new algorithmic approach to the general Lov�sz local lemma
- A result on linear coloring of planar graphs
- Asymptotically optimal frugal colouring
- Star Chromatic Index
- Separation dimension and degree
- Paint cost and the frugal distinguishing number
- A general framework for hypergraph coloring
- Complexity dichotomy for list-5-coloring with a forbidden induced subgraph
- Better bounds for poset dimension and boxicity
- On a theorem about vertex colorings of graphs
- Distributed algorithms for the Lovász local lemma and graph coloring
- Counting colorings of triangle-free graphs
- Improved bounds on linear coloring of plane graphs
- Upper bounds on the linear chromatic number of a graph
- k-forested coloring of planar graphs with large girth
- Frugal, acyclic and star colourings of graphs
- Linear and 2-frugal choosability of graphs of small maximum average degree
- Proper conflict-free coloring of graphs with large maximum degree
- Brooks-type theorem for r-frugal coloring of graphs
- \(k\)-forested choosability of planar graphs and sparse graphs
- Linear choosability of graphs
- Asymptotically optimal frugal colouring
- Chromatic coloring with a maximum color class
This page was built for publication: Colouring a graph frugally
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1280272)
