A survey on the distance-colouring of graphs
---
paper_title: Un probleme de coloration des sommets d''un graphe

paper_content:

A system for venting smoke and fumes from selected floors of a multi-story building comprising a vertical smoke pipe or shaft which extends from the basement to the roof of the building and a plurality of vent units disposed along the smoke shaft, one being associated with each floor of the building. Each unit includes a hinged door that opens by gravity force and is normally maintained closed by a latch mechanism that may be operated remotely by electrical or pneumatic means or may be operated manually. A thin metallic gasket seals the door to its frame and further functions as a spring means for urging the door open when the latch mechanism is released.
---
paper_title: Graph coloring problems

paper_content:

Planar Graphs. Graphs on Higher Surfaces. Degrees. Critical Graphs. The Conjectures of Hadwiger and Hajos. Sparse Graphs. Perfect Graphs. Geometric and Combinatorial Graphs. Algorithms. Constructions. Edge Colorings. Orientations and Flows. Chromatic Polynomials. Hypergraphs. Infinite Chromatic Graphs. Miscellaneous Problems. Indexes.
---
paper_title: On the Generalized Chromatic Number

paper_content:

The chromatic number relative to distance p, denoted by (p, G) is the minimum number of colors sufficing for coloring the vertices of G in such a way that any two vertices of distance not greater than p have distinct colors. We give upper bounds for the chromatic number (3, G) for bipartite (planar) graphs and generalize a result of S. Antonucci giving a lower bound for (2, G).
---
paper_title: Local structures in plane maps and distance colourings

paper_content:

Abstract A structural result on normal plane maps is presented. It strengthens a result by Borodin which is related to Kotzig's and Lebesgue's classical results. Then the t-distance chromatic number of a planar graph G with maximum degree Δ ( G )⩽ D where D ⩾8 is proved to be bounded above by a polynomial in D of degree t −1.
---
paper_title: Un probleme de coloration des sommets d''un graphe

paper_content:

A system for venting smoke and fumes from selected floors of a multi-story building comprising a vertical smoke pipe or shaft which extends from the basement to the roof of the building and a plurality of vent units disposed along the smoke shaft, one being associated with each floor of the building. Each unit includes a hinged door that opens by gravity force and is normally maintained closed by a latch mechanism that may be operated remotely by electrical or pneumatic means or may be operated manually. A thin metallic gasket seals the door to its frame and further functions as a spring means for urging the door open when the latch mechanism is released.
---
paper_title: Graph coloring problems

paper_content:

Planar Graphs. Graphs on Higher Surfaces. Degrees. Critical Graphs. The Conjectures of Hadwiger and Hajos. Sparse Graphs. Perfect Graphs. Geometric and Combinatorial Graphs. Algorithms. Constructions. Edge Colorings. Orientations and Flows. Chromatic Polynomials. Hypergraphs. Infinite Chromatic Graphs. Miscellaneous Problems. Indexes.
---
paper_title: On the Generalized Chromatic Number

paper_content:

The chromatic number relative to distance p, denoted by (p, G) is the minimum number of colors sufficing for coloring the vertices of G in such a way that any two vertices of distance not greater than p have distinct colors. We give upper bounds for the chromatic number (3, G) for bipartite (planar) graphs and generalize a result of S. Antonucci giving a lower bound for (2, G).
---
paper_title: On the Generalized Chromatic Number

paper_content:

The chromatic number relative to distance p, denoted by (p, G) is the minimum number of colors sufficing for coloring the vertices of G in such a way that any two vertices of distance not greater than p have distinct colors. We give upper bounds for the chromatic number (3, G) for bipartite (planar) graphs and generalize a result of S. Antonucci giving a lower bound for (2, G).
---
paper_title: Distant Vertex Partitions of Graphs

paper_content:

We consider the function χ(Gk), defined to be the smallest number of colours that can colour a graph G in such a way that no vertices of distance at most k receive the same colour. In particular we shall look at how small a value this function can take in terms of the order and diameter of G. We get general bounds for this and tight bounds for the cases k=2 and k=3.
---
paper_title: Drawing Graphs in the Plane with High Resolution

paper_content:

This paper presents the problem of drawing a graph in the plane so that edges appear as straight lines and the minimum angle formed by any pair of incident edges is maximized. The resolution of a layout is defined to be the size of the minimum angle formed by incident edges of the graph, and the resolution of a graph to be the maximum resolution of any layout of the graph. The resolution R of a graph is characterized in terms of the maximum node degree d of the graph by proving that $\Omega (\frac{1}{{d^2 }}) \leqslant R \leqslant \frac{{2\pi }}{d}$ for any graph. Moreover, it is proved that $R = \Theta (\frac{1}{d})$ for many graphs including planar graphs, complete graphs, hypercubes, multidimensional meshes and tori, and other special networks. It is also shown that the problem of deciding if $R = \frac{{2\pi }}{d}$ for a graph is NP-hard for $d = 4$, and by using a counting argument that $R = O(\frac{{\log d}}{{d^2 }})$ for many graphs.
---
paper_title: Acyclic and k-distance coloring of the grid

paper_content:

In this paper, we give a relatively simple though very efficient way to color the d-dimensional grid G(n1,n2,...,nd) (with ni vertices in each dimension 1 ≤ i ≤ d), for two different types of vertex colorings: (1) acyclic coloring of graphs, in which we color the vertices such that (i) no two neighbors are assigned the same color and (ii) for any two colors i and j, the subgraph induced by the vertices colored i or j is acyclic; and (2) k-distance coloring of graphs, in which every vertex must be colored in such a way that two vertices lying at distance less than or equal to k must be assigned different colors. The minimum number of colors needed to acyclically color (respectively k-distance color) a graph G is called acyclic chromatic number of G (respectively k-distance chromatic number), and denoted a(G) (respectively χk(G)).The method we propose for coloring the d-dimensional grid in those two variants relies on the representation of the vertices of Gd(n1,...,nd) thanks to its coordinates in each dimension; this gives us upper bounds on a(Gd(n1,...,nd)) and χk(Gd(n1,...,nd)).We also give lower bounds on a(Gd(n1,...,nd)) and χk(Gd(n1,...,nd)). In particular, we give a lower bound on a(G) for any graph G; surprisingly, as far as we know this result was never mentioned before. Applied to the d-dimensional grid Gd(n1,...,nd), the lower and upper bounds for a(Gd(n1,...,nd)) match (and thus give an optimal result) when the lengths in each dimension are "sufficiently large" (more precisely, if Σ i=1d 1/ni ≤ 1). If this is not the case, then these bounds differ by an additive constant at most equal to 1- ⌊Σi=1d1/ni⌋. Concerning χk(Gd(n1,...,nd)), we give exact results on its value for (1) k = 2 and any d ≥ 1, and (2) d = 2 and any k ≥ 1.In the case of acyclic coloring, we also apply our results to hypercubes of dimension d, Hd, which are a particular case of Gd(n1,...,nd) in which there are only 2 vertices in each dimension. In that case, the bounds we obtain differ by a multiplicative constant equal to 2.
---
paper_title: DISTANCE COLORING OF THE HEXAGONAL LATTICE

paper_content:

Motivated by the frequency assignment problem we study the d-distant coloring of the vertices of an infinite plane hexagonal lattice H. Let d be a positive integer. A d-distant coloring of the lattice H is a coloring of the vertices of H such that each pair of vertices distance at most d apart have different colors. The d-distant chromatic number of H, denoted χd(H), is the minimum number of colors needed for a d-distant coloring of H. We give the exact value of χd(H) for any d odd and estimations for any d even.
---

Title: A Survey on the Distance-Colouring of Graphs

Section 1: Introduction
Description 1: Write an overview of distance-colouring in graphs, including definitions, historical context, and scope of the survey.

Section 2: Results
Description 2: Summarize key findings in the field of distance-colouring, including known characterizations, conjectures, and open problems.

Section 3: Graphs for Distance-Colouring
Description 3: Describe specific types of graphs studied in distance-colouring, such as planar graphs, Moore graphs, and others.

Section 4: Upper Bounds
Description 4: Present upper bound results for the distance-chromatic number of different classes of graphs.

Section 5: Applications
Description 5: Discuss practical applications of distance-colouring, particularly in problems like frequency assignment in radio transmissions.

Section 6: Conclusion
Description 6: Summarize the state of the field, key takeaways, and potential future research directions.