Jump to content

User:2bitdinosaur/sandbox

From Wikipedia, the free encyclopedia
The 2-centered chromatic number of the Dyck graph is 4, while its chromatic number is 2.

In graph theory, p-centered colorings are a generalization of proper vertex colorings and form one of the families of parameters that mathematically formalize the notion of graph sparsity.[1] The concept was originally introduced as a local approximation of centered colorings. One of the main reasons for studying graph sparsity stems from the desire to develop efficient algorithms for problems which are computationally hard when no structural restrictions are posed on the underlying graph. This, in turn, has naturally lead to the introduction of the class of graphs of bounded expansion and the class of graphs which are nowhere dense. These properties are weak enough to allow us to capture a wide assortment of graphs, such as the class of graphs excluding a fixed minor or graphs of bounded book-thickness, yet rich enough to capture enough structure to allow for the implementation of efficient algorithms. For instance, Dvořák, Kráľ and Thomas have devised an FPT algorithm for testing first-order definable properties in graph classes of bounded expansion.[2]

Definition

[edit]

A vertex coloring φ of a graph G is p-centered if for every connected subgraph H of G, either:

  1. φ uses more than p colors on G or
  2. there is a color that appears exactly once in H

For p=1, the definition of 1-centered colorings coincides with the one for proper vertex colorings, as each edge induces an isomorphic copy of , the complete graph on 2 vertices, which must receive 2 distinct colors under φ.

The 2-centered colorings of a graph G are exactly its star colorings.

An arbitrary graph G can always be colored in a p-centered manner for any simply by assigning each vertex a unique color.

The p-chromatic number of G is by definition the smallest number of colors necessary for a p-centered coloring of G and is denoted by .

A p-centered coloring of G is also a treedepth-p coloring. This fact underpins the importance of p-centered colorings, as low treedepth colorings are a central tool in designing parameterized algorithms in classes of bounded expansion. The running time of algorithms based on p-centered colorings clearly depends on the number of colors used. Therefore, designing efficient coloring procedures with as few colors as possible is desirable.[1]

Relation to bounded expansion

[edit]

p-centered colorings play an important role in structural graph theory, as they allow for an equivalent description for when a graph class is of bounded expansion, a concept originally defined in terms of maximum densities of shallow minors.[3] Nešetřil and Ossona de Mendez, who first introduced the notion of bounded expansion, have proven that a graph class C is of bounded expansion if and only if for every integer and every graph G in C there exists a function such that . Thus, the function f offers a uniform bound on the p-chromatic number over the entire class G.

Properties

[edit]

Upper bounds on the p-centered chromatic number

[edit]

If G is an arbitrary graph, then is a trivial upper bound on . However, restricting our attention to some special proper subclasses of the class of all graphs, we may obtain a uniform upper bound on which depends only on the parameter p and the class C, but not on the graph G itself. The following bounds are due to Dębski, Felsner, Micek, and Schröder[1]:

  1. Planar graphs admit p-centered colorings with colors.
  2. Graphs with Euler genus g admit p-centered colorings with colors.
  3. Graphs with bounded degree admit p-centered colorings with colors. Specifically, if G has maximum degree at most , then
  4. For every graph H there is a polynomial f such that the graphs excluding H as a topological minor admit p-centered colorings with at most colors.
  5. Outerplanar graphs admit p-centered colorings with colors.
  6. Planar graphs of treewidth at most 3 admit p-centered colorings with colors.
  7. Graphs of simple treewidth at most k admit p-centered colorings with colors.

All of the above mentioned bounds are also supported by polynomial time algorithms that may compute the coloring.

Moreover, Pilipczuk and Siebert have shown that for every , , every graph G of treewidth at most t has .[4]

Lower bounds on the p-centered chromatic number

[edit]

Since a p-centered coloring of a graph G is also a proper coloring, we always have . Similarly to the results above, in some situations we may also bound the p-chromatic number from below, more specifically:

  1. There is a family of outerplanar graphs that require colors in any p-centered coloring.
  2. There is a family of planar graphs of treewidth 3 that require colors in any p-centered coloring.
  3. There is a family of graphs of simple treewidth k that require colors in any p-centered coloring.
  4. For any and there is a graph of treewidth at most t with . This implies that the upper bound proposed by Pilipczuk and Siebert is indeed sharp.

References

[edit]
  1. ^ a b c Michał Dębski, Stefan Felsner, Piotr Micek, and Felix Schröder. Improved bounds for centered colorings. In Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA ’20, pages 2212–2226, 2020
  2. ^ Zdeněk Dvořák, Daniel Král, and Robin Thomas. Testing first-order properties for subclasses of sparse graphs. Journal of the ACM, 60(5), 2013.
  3. ^ Jaroslav Nešetřil and Patrice Ossona de Mendez. Grad and classes with bounded expansion. I. Decompositions. European Journal of Combinatorics, 29(3):760–776, 2008.
  4. ^ Michał Pilipczuk and Sebastian Siebertz. Polynomial bounds for centered colorings on proper minor-closed graph classes. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’19, pages 1501–1520, 2019.