# Restricted colorings of graphs

@inproceedings{Alon1993RestrictedCO, title={Restricted colorings of graphs}, author={Noga Alon}, year={1993} }

Abstract The problem of properly coloring the vertices (or edges) of a graph using for each vertex (or edge) a color from a prescribed list of permissible colors, received a considerable amount of attention. Here we describe the techniques applied in the study of this subject, which combine combinatorial, algebraic and probabilistic methods, and discuss several intriguing conjectures and open problems. This is mainly a survey of recent and less recent results in the area, but it contains… Expand

#### 214 Citations

List-coloring and sum-list-coloring problems on graphs

- Mathematics
- 2012

Graph coloring is a well-known and well-studied area of graph theory that has many applications. In this dissertation, we look at two generalizations of graph coloring known as list-coloring and… Expand

Packing list-colourings

- Computer Science, Mathematics
- ArXiv
- 2021

The study of a natural strengthening of list colouring, where instead of one list-colouring, the seek many in parallel, is initiated, which has taken inspiration from study of the strong chromatic number. Expand

On the complexity of some colorful problems parameterized by treewidth

- Mathematics
- 2011

In this paper, we study the complexity of several coloring problems on graphs, parameterized by the treewidth of the graph.1.The List Coloring problem takes as input a graph G, together with an… Expand

On the Complexity of Some Colorful Problems Parameterized by Treewidth

- Computer Science, Mathematics
- COCOA
- 2007

The problem of determining whether χl(G) ≤ r, the LIST CHROMATIC NUMBER problem, is solvable in linear time for every fixed treewidth bound t, and a list-based variation, LIST EQUITABLE COLORING is W[1]-hard for trees, parameterized by the number of colors on the lists. Expand

Computing the list chromatic index of graphs

- Mathematics, Computer Science
- J. Discrete Algorithms
- 2018

A corollary to the Quantitative Combinatorial Nullstellensatz that explains a well-known connection between the sign of 1-factorizations (edge colorings) and the List Edge Coloring Conjecture and shows that the product over all signs of all the 1-factors in a 1- Factorization is the product of that 1-Factorization. Expand

Graph colorings with local constraints - a survey

- Mathematics, Computer Science
- Discuss. Math. Graph Theory
- 1997

This work surveys the literature on those variants of the chromatic number problem where not only a proper coloring has to be found but some further local restrictions are imposed on the color assignment. Expand

AN UPPER BOUND ON THE LIST CHROMATIC NUMBER OF LOCALLY SPARSE GRAPHS

- 2001

Suppose that G is a graph with maximum degree ∆ and for every vertex v in G, the neighborhood of v contains at most ∆2/f edges. We prove that the list chromatic number of G is at most K∆/ log f , for… Expand

A General Upper Bound on the List Chromatic Number of Locally Sparse Graphs

- Computer Science, Mathematics
- Combinatorics, Probability and Computing
- 2002

Several upper bounds for the strong (list) chromatic index of a graph are derived, under various assumptions, and this result is sharp up to the multiplicative constant K and strengthens previous results by Kim, Johansson, Alon, Krivelevich and Sudakov. Expand

Graph polynomials and paintability of plane graphs

- Mathematics
- 2020

There exists a variety of coloring problems for plane graphs, involving vertices, edges, and faces in all possible combinations. For instance, in the \emph{entire coloring} of a plane graph we are to… Expand

The potential to improve the choice: list conflict-free coloring for geometric hypergraphs

- Computer Science, Mathematics
- SoCG '11
- 2011

This work provides an algorithm, such that, given a family of lists with the appropriate sizes, the algorithm produces a stronger unique-maximum coloring, in which colors are positive integers and the maximum color in every hyperedge occurs uniquely. Expand

#### References

SHOWING 1-10 OF 59 REFERENCES

Some results concerning the complexity of restricted colorings of graphs

- Computer Science, Mathematics
- Discret. Appl. Math.
- 1992

Some evidence is obtained for comparing the complexity of the restricted vertex coloring problem versus that of edge coloring and a number of results are arrived at about special cases that are either positive (polynomial solvability) or negative (NP-completeness proofs). Expand

Choice Numbers of Graphs: a Probabilistic Approach

- Mathematics, Computer Science
- Comb. Probab. Comput.
- 1992

It is shown that there are two positive constants c 1 and c 2 such that for all m ≥ 2 and r ≥ 2 the choice number of the complete r -partite graph with m vertices in each vertex class is between c 1 r log m and c2 c log m. Expand

Colorings and orientations of graphs

- Mathematics, Computer Science
- Comb.
- 1992

Bounds for the chromatic number and for some related parameters of a graph are obtained by applying algebraic techniques by proving that there is a legal vertex-coloring of G assigning to each vertexv a color fromS(v). Expand

The number of edge 3-colorings of a planar cubic graph as a permanent

- Computer Science, Mathematics
- Discret. Math.
- 1974

The number of edge 3-colorings of a finite planar cubic graph G is established to be equal to 2^-^N|Permanent(A)|, where N is the number of edges of G, and A is the 2N x 2N square matrix formed by repeating each row of the N x2N vertex-directed edge incidence matrix of H (with an arbitrary orientation). Expand

Bounding the Independence Number of a Graph

- Mathematics
- 1982

Publisher Summary This chapter discusses an idea that might suggest some non-trivial approaches to NP-complete problems. The problem of computing the independence number of a graph is NP-complete.… Expand

On the penrose number of cubic diagrams

- Computer Science, Mathematics
- Discret. Math.
- 1989

A new recursive scheme for the computation of the Penrose number is yielded, which gives the number of vertex-4- colorings of a loopless plane triangulation in terms of the mappings from the vertex-set to {1,2,3} which take exactly two distinct values on each triangle. Expand

On the number of list-colorings

- Mathematics, Computer Science
- J. Graph Theory
- 1992

It will follow in particular that F(G, k) is not given by a polynominal in k for all G, and the proof is based on the analysis of an algorithm for computing f (G, L) analogous to the classical one for computing P( G, k). Expand

An upper bound for the total chromatic number of dense graphs

- Mathematics, Computer Science
- J. Graph Theory
- 1992

A result of Hajnal and Szemeredi concerning equitable vertex-colorings and an adaptation of the standard proof of Vizing's Theorem are used to show that if the maximum degree of a graph G satisfies Δ(G) ≥ |V(G)/k, then X″(G), which is an improvement on the currently available upper bounds for dense graphs having large order. Expand

An upper bound for the total chromatic number

- Mathematics, Computer Science
- Graphs Comb.
- 1990

AbstractThe total chromatic number,χ″(G), of a graphG, is defined to be the minimum number of colours needed to colour the vertices and edges of a graph in such a way that no adjacent vertices, no… Expand

Graphs and Hypergraphs

- 2021

Independence densities of hypergraphs We consider the number of independent sets in hypergraphs, which allows us to define the independence density of countable hypergraphs. Hypergraph independence… Expand