Grundy number

Last updated
An optimal greedy coloring (left) and Grundy coloring (right) of a crown graph. The numbers indicate the order in which the greedy algorithm colors the vertices. Greedy colourings.svg
An optimal greedy coloring (left) and Grundy coloring (right) of a crown graph. The numbers indicate the order in which the greedy algorithm colors the vertices.

In graph theory, the Grundy number or Grundy chromatic number of an undirected graph is the maximum number of colors that can be used by a greedy coloring strategy that considers the vertices of the graph in sequence and assigns each vertex its first available color, using a vertex ordering chosen to use as many colors as possible. Grundy numbers are named after P. M. Grundy, who studied an analogous concept for directed graphs in 1939. [1] The undirected version was introduced by Christen & Selkow (1979). [2]

Contents

Examples

The path graph with four vertices provides the simplest example of a graph whose chromatic number differs from its Grundy number. This graph can be colored with two colors, but its Grundy number is three: if the two endpoints of the path are colored first, the greedy coloring algorithm will use three colors for the whole graph. [3]

The complete bipartite graphs are the only connected graphs whose Grundy number is two. All other connected graphs contain either a triangle or a four-vertex path, which cause the Grundy number to be at least three. [3]

The crown graphs are obtained from complete bipartite graphs by removing a perfect matching. As a result, for each vertex on one side of the bipartition, there is exactly one vertex on the opposite side of the bipartition that it is not adjacent to. As bipartite graphs, they can be colored with two colors, but their Grundy number is : if a greedy coloring algorithm considers each matched pair of vertices in order, each pair will receive a different color. As this example shows, the Grundy number can be larger than the chromatic number by a factor linear in the number of graph vertices. [4]

Atoms

Zaker (2006) defines a sequence of graphs called t-atoms, with the property that a graph has Grundy number at least t if and only if it contains a t-atom. Each t-atom is formed from an independent set and a (t− 1)-atom, by adding one edge from each vertex of the (t− 1)-atom to a vertex of the independent set, in such a way that each member of the independent set has at least one edge incident to it. A Grundy coloring of a t-atom can be obtained by coloring the independent set first with the smallest-numbered color, and then coloring the remaining (t− 1)-atom with an additional t− 1 colors. For instance, the only 1-atom is a single vertex, and the only 2-atom is a single edge, but there are two possible 3-atoms: a triangle and a four-vertex path. [3]

In sparse graphs

For a graph with n vertices and degeneracy d, the Grundy number is O(d log n). In particular, for graphs of bounded degeneracy (such as planar graphs) or graphs for which the chromatic number and degeneracy are bounded within constant factors of each other (such as chordal graphs) the Grundy number and chromatic number are within a logarithmic factor of each other. [5] For interval graphs, the chromatic number and Grundy number are within a factor of 8 of each other. [6]

Computational complexity

Testing whether the Grundy number of a given graph is at least k, for a fixed constant k, can be performed in polynomial time, by searching for all possible k-atoms that might be subgraphs of the given graph. However, this algorithm is not fixed-parameter tractable, because the exponent in its running time depends on k. When k is an input variable rather than a parameter, the problem is NP-complete. [3] The Grundy number is at most one plus the maximum degree of the graph, and it remains NP-complete to test whether it equals one plus the maximum degree. [7] There exists a constant c > 1 such that it is NP-hard under randomized reductions to approximate the Grundy number to within an approximation ratio better than c. [8]

There is an exact exponential time algorithm for the Grundy number that runs in time O(2.443n). [9]

For trees, and graphs of bounded treewidth, the Grundy number may be unboundedly large. [10] Nevertheless, the Grundy number can be computed in polynomial time for trees, and is fixed-parameter tractable when parameterized by both the treewidth and the Grundy number, [11] although (assuming the exponential time hypothesis) the dependence on treewidth must be greater than singly exponential. [9] When parameterized only by the Grundy number, it can be computed in fixed-parameter tractable time for chordal graphs and claw-free graphs, [9] and also (using general results on subgraph isomorphism in sparse graphs to search for atoms) for graphs of bounded expansion. [9] [12] [13] However, on general graphs the problem is W[1]-hard when parameterized by the Grundy number. [14]

Well-colored graphs

A graph is called well-colored if its Grundy number equals its chromatic number. Testing whether a graph is well-colored is coNP-complete. [3] The hereditarily well-colored graphs (graphs for which every induced subgraph is well-colored) are exactly the cographs, the graphs that do not have a four-vertex path as an induced subgraph. [2]

Related Research Articles

<span class="mw-page-title-main">Bipartite graph</span> Graph divided into two independent sets

In the mathematical field of graph theory, a bipartite graph is a graph whose vertices can be divided into two disjoint and independent sets and , that is, every edge connects a vertex in to one in . Vertex sets and are usually called the parts of the graph. Equivalently, a bipartite graph is a graph that does not contain any odd-length cycles.

This is a glossary of graph theory. Graph theory is the study of graphs, systems of nodes or vertices connected in pairs by lines or edges.

<span class="mw-page-title-main">Perfect graph theorem</span> An undirected graph is perfect if and only if its complement graph is also perfect

In graph theory, the perfect graph theorem of László Lovász states that an undirected graph is perfect if and only if its complement graph is also perfect. This result had been conjectured by Berge, and it is sometimes called the weak perfect graph theorem to distinguish it from the strong perfect graph theorem characterizing perfect graphs by their forbidden induced subgraphs.

<span class="mw-page-title-main">Graph homomorphism</span> A structure-preserving correspondence between node-link graphs

In the mathematical field of graph theory, a graph homomorphism is a mapping between two graphs that respects their structure. More concretely, it is a function between the vertex sets of two graphs that maps adjacent vertices to adjacent vertices.

<span class="mw-page-title-main">Edge coloring</span> Problem of coloring a graphs edges such that meeting edges do not match

In graph theory, a proper edge coloring of a graph is an assignment of "colors" to the edges of the graph so that no two incident edges have the same color. For example, the figure to the right shows an edge coloring of a graph by the colors red, blue, and green. Edge colorings are one of several different types of graph coloring. The edge-coloring problem asks whether it is possible to color the edges of a given graph using at most k different colors, for a given value of k, or with the fewest possible colors. The minimum required number of colors for the edges of a given graph is called the chromatic index of the graph. For example, the edges of the graph in the illustration can be colored by three colors but cannot be colored by two colors, so the graph shown has chromatic index three.

<span class="mw-page-title-main">Chordal graph</span> Graph where all long cycles have a chord

In the mathematical area of graph theory, a chordal graph is one in which all cycles of four or more vertices have a chord, which is an edge that is not part of the cycle but connects two vertices of the cycle. Equivalently, every induced cycle in the graph should have exactly three vertices. The chordal graphs may also be characterized as the graphs that have perfect elimination orderings, as the graphs in which each minimal separator is a clique, and as the intersection graphs of subtrees of a tree. They are sometimes also called rigid circuit graphs or triangulated graphs.

<span class="mw-page-title-main">Circle graph</span> Intersection graph of a chord diagram

In graph theory, a circle graph is the intersection graph of a chord diagram. That is, it is an undirected graph whose vertices can be associated with a finite system of chords of a circle such that two vertices are adjacent if and only if the corresponding chords cross each other.

<span class="mw-page-title-main">Hadwiger number</span> Size of largest complete graph made by contracting edges of a given graph

In graph theory, the Hadwiger number of an undirected graph G is the size of the largest complete graph that can be obtained by contracting edges of G. Equivalently, the Hadwiger number h(G) is the largest number n for which the complete graph Kn is a minor of G, a smaller graph obtained from G by edge contractions and vertex and edge deletions. The Hadwiger number is also known as the contraction clique number of G or the homomorphism degree of G. It is named after Hugo Hadwiger, who introduced it in 1943 in conjunction with the Hadwiger conjecture, which states that the Hadwiger number is always at least as large as the chromatic number of G.

In graph theory, the metric dimension of a graph G is the minimum cardinality of a subset S of vertices such that all other vertices are uniquely determined by their distances to the vertices in S. Finding the metric dimension of a graph is an NP-hard problem; the decision version, determining whether the metric dimension is less than a given value, is NP-complete.

In graph theory, the treewidth of an undirected graph is an integer number which specifies, informally, how far the graph is from being a tree. The smallest treewidth is 1; the graphs with treewidth 1 are exactly the trees and the forests. The graphs with treewidth at most 2 are the series–parallel graphs. The maximal graphs with treewidth exactly k are called k-trees, and the graphs with treewidth at most k are called partial k-trees. Many other well-studied graph families also have bounded treewidth.

<span class="mw-page-title-main">Clique-width</span> Measure of graph complexity

In graph theory, the clique-width of a graph G is a parameter that describes the structural complexity of the graph; it is closely related to treewidth, but unlike treewidth it can be small for dense graphs. It is defined as the minimum number of labels needed to construct G by means of the following 4 operations :

  1. Creation of a new vertex v with label i (denoted by i(v))
  2. Disjoint union of two labeled graphs G and H (denoted by )
  3. Joining by an edge every vertex labeled i to every vertex labeled j (denoted by η(i,j)), where i ≠ j
  4. Renaming label i to label j (denoted by ρ(i,j))
<span class="mw-page-title-main">Greedy coloring</span> One-by-one assignment of colors to graph vertices

In the study of graph coloring problems in mathematics and computer science, a greedy coloring or sequential coloring is a coloring of the vertices of a graph formed by a greedy algorithm that considers the vertices of the graph in sequence and assigns each vertex its first available color. Greedy colorings can be found in linear time, but they do not, in general, use the minimum number of colors possible.

In graph theory, an area of mathematics, an equitable coloring is an assignment of colors to the vertices of an undirected graph, in such a way that

In graph theory, the tree-depth of a connected undirected graph is a numerical invariant of , the minimum height of a Trémaux tree for a supergraph of . This invariant and its close relatives have gone under many different names in the literature, including vertex ranking number, ordered chromatic number, and minimum elimination tree height; it is also closely related to the cycle rank of directed graphs and the star height of regular languages. Intuitively, where the treewidth of a graph measures how far it is from being a tree, this parameter measures how far a graph is from being a star.

<span class="mw-page-title-main">Degeneracy (graph theory)</span> Measurement of graph sparsity

In graph theory, a k-degenerate graph is an undirected graph in which every subgraph has a vertex of degree at most k: that is, some vertex in the subgraph touches k or fewer of the subgraph's edges. The degeneracy of a graph is the smallest value of k for which it is k-degenerate. The degeneracy of a graph is a measure of how sparse it is, and is within a constant factor of other sparsity measures such as the arboricity of a graph.

<span class="mw-page-title-main">1-planar graph</span>

In topological graph theory, a 1-planar graph is a graph that can be drawn in the Euclidean plane in such a way that each edge has at most one crossing point, where it crosses a single additional edge. If a 1-planar graph, one of the most natural generalizations of planar graphs, is drawn that way, the drawing is called a 1-plane graph or 1-planar embedding of the graph.

<span class="mw-page-title-main">Graph power</span> Graph operation: linking all pairs of nodes of distance ≤ k

In graph theory, a branch of mathematics, the kth powerGk of an undirected graph G is another graph that has the same set of vertices, but in which two vertices are adjacent when their distance in G is at most k. Powers of graphs are referred to using terminology similar to that of exponentiation of numbers: G2 is called the square of G, G3 is called the cube of G, etc.

<span class="mw-page-title-main">Odd cycle transversal</span>

In graph theory, an odd cycle transversal of an undirected graph is a set of vertices of the graph that has a nonempty intersection with every odd cycle in the graph. Removing the vertices of an odd cycle transversal from a graph leaves a bipartite graph as the remaining induced subgraph.

<span class="mw-page-title-main">Well-colored graph</span>

In graph theory, a subfield of mathematics, a well-colored graph is an undirected graph for which greedy coloring uses the same number of colors regardless of the order in which colors are chosen for its vertices. That is, for these graphs, the chromatic number and Grundy number are equal.

The twin-width of an undirected graph is a natural number associated with the graph, used to study the parameterized complexity of graph algorithms. Intuitively, it measures how similar the graph is to a cograph, a type of graph that can be reduced to a single vertex by repeatedly merging together twins, vertices that have the same neighbors. The twin-width is defined from a sequence of repeated mergers where the vertices are not required to be twins, but have nearly equal sets of neighbors.

References

  1. ↑ Grundy, P. M. (1939), "Mathematics and games", Eureka , 2: 6–8, archived from the original on 2007-09-27. As cited by Erdős, Paul; Hedetniemi, Stephen T.; Laskar, Renu C.; Prins, Geert C. E. (2003), "On the equality of the partial Grundy and upper ochromatic numbers of graphs", Discrete Mathematics, 272 (1): 53–64, doi: 10.1016/S0012-365X(03)00184-5 , MR   2019200 .
  2. 1 2 Christen, Claude A.; Selkow, Stanley M. (1979), "Some perfect coloring properties of graphs", Journal of Combinatorial Theory , Series B, 27 (1): 49–59, doi: 10.1016/0095-8956(79)90067-4 , MR   0539075 .
  3. 1 2 3 4 5 Zaker, Manouchehr (2006), "Results on the Grundy chromatic number of graphs", Discrete Mathematics , 306 (23): 3166–3173, doi: 10.1016/j.disc.2005.06.044 , MR   2273147 .
  4. ↑ Johnson, D. S. (1974), "Worst-case behavior of graph coloring algorithms", Proc. 5th Southeastern Conf. on Combinatorics, Graph Theory, and Computing, Utilitas Mathematicae, Winnipeg, pp. 513–527, MR   0389644 {{citation}}: CS1 maint: location missing publisher (link)
  5. ↑ Irani, Sandy (1994), "Coloring inductive graphs on-line", Algorithmica, 11 (1): 53–72, doi:10.1007/BF01294263, MR   1247988, S2CID   181800 .
  6. ↑ Narayanaswamy, N. S.; Subhash Babu, R. (2008), "A note on first-fit coloring of interval graphs", Order, 25 (1): 49–53, doi:10.1007/s11083-008-9076-6, MR   2395157, S2CID   207223738 .
  7. ↑ Havet, Frédéric; Sampaio, Leonardo (2010), "On the Grundy number of a graph", Parameterized and exact computation, Lecture Notes in Comput. Sci., vol. 6478, Springer, Berlin, pp. 170–179, Bibcode:2010LNCS.6478..170H, doi:10.1007/978-3-642-17493-3_17, ISBN   978-3-642-17492-6, MR   2770795 .
  8. ↑ Kortsarz, Guy (2007), "A lower bound for approximating Grundy numbering", Discrete Mathematics & Theoretical Computer Science, 9 (1).
  9. 1 2 3 4 Bonnet, Édouard; Foucaud, Florent; Kim, Eun Jung; Sikora, Florian (2015), "Complexity of Grundy coloring and its variants", Computing and combinatorics, Lecture Notes in Comput. Sci., vol. 9198, Springer, Cham, pp. 109–120, arXiv: 1407.5336 , doi:10.1007/978-3-319-21398-9_9, ISBN   978-3-319-21397-2, MR   3447246, S2CID   5514223 .
  10. ↑ Gyárfás, A.; Lehel, J. (1988), "On-line and first fit colorings of graphs", Journal of Graph Theory, 12 (2): 217–227, doi:10.1002/jgt.3190120212, MR   0940831, S2CID   8839035 .
  11. ↑ Telle, Jan Arne; Proskurowski, Andrzej (1997), "Algorithms for vertex partitioning problems on partial k-trees", SIAM Journal on Discrete Mathematics , 10 (4): 529–550, CiteSeerX   10.1.1.25.152 , doi:10.1137/S0895480194275825, MR   1477655 .
  12. ↑ Dvořák, Zdeněk; Kráľ, Daniel; Thomas, Robin (2010), "Deciding first-order properties for sparse graphs", Proc. 51st Annual IEEE Symposium on Foundations of Computer Science (FOCS 2010), IEEE Computer Soc., Los Alamitos, CA, pp. 133–142, MR   3024787 .
  13. ↑ Nešetřil, Jaroslav; Ossona de Mendez, Patrice (2012), "18.3 The Subgraph Isomorphism Problem and Boolean Queries", Sparsity: Graphs, Structures, and Algorithms, Algorithms and Combinatorics, vol. 28, Springer, pp. 400–401, doi:10.1007/978-3-642-27875-4, ISBN   978-3-642-27874-7, MR   2920058 .
  14. ↑ Aboulker, Pierre; Bonnet, Edouard; Kim, Eun Jung; Sikora, Florian (2023), "Grundy Coloring and Friends, Half-Graphs, Bicliques", Algorithmica , 85: 1–28, doi:10.1007/s00453-022-01001-2, S2CID   250614665 .
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.