Chromatic numbers of exact distance graphs

DOI10.1016/J.JCTB.2018.05.007MaRDI QIDQ1633747zbMATH OpenOpenAlexFDO

Authors Jan van den Heuvel, Daniel A. Quiroz, H. A. Kierstead

Publication date 20 December 2018

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1612.02160, http://eprints.lse.ac.uk/88134/1/van%20den%20Heuvel_Chromatic%20Numbers_Accepted.pdf

zbMATH Keywords

chromatic numberplanar graphsbounded expansionexact distance graphsgeneralised colouring numbers

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Distance in graphs (05C12) Coloring of graphs and hypergraphs (05C15)

Abstract: For any graph $G=(V,E)$ and positive integer $p$, the exact distance-$p$ graph $G^{[aturalp]}$ is the graph with vertex set $V$, which has an edge between vertices $x$ and $y$ if and only if $x$ and $y$ have distance $p$ in $G$. For odd $p$, Nev{s}etv{r}il and Ossona de Mendez proved that for any fixed graph class with bounded expansion, the chromatic number of $G^{[aturalp]}$ is bounded by an absolute constant. Using the notion of generalised colouring numbers, we give a much simpler proof for the result of Nev{s}etv{r}il and Ossona de Mendez, which at the same time gives significantly better bounds. In particular, we show that for any graph $G$ and odd positive integer $p$, the chromatic number of $G^{[aturalp]}$ is bounded by the weak $(2p-1)$-colouring number of $G$. For even $p$, we prove that $chi(G^{[aturalp]})$ is at most the weak $(2p)$-colouring number times the maximum degree. For odd $p$, the existing lower bound on the number of colours needed to colour $G^{[aturalp]}$ when $G$ is planar is improved. Similar lower bounds are given for $K_t$-minor free graphs.

Recommendations

• Colouring exact distance graphs of chordal graphs
• Exact distance colouring in trees
• scientific article; zbMATH DE number 3968609
• Colouring graphs with bounded generalized colouring number
• The odd-distance plane graph

Cites work

• scientific article; zbMATH DE number 3265667 (Why is no real title available?)
• scientific article; zbMATH DE number 3308991 (Why is no real title available?)
• A short note about pursuit games played on a graph with a given genus
• A simple competitive graph coloring algorithm
• A survey on the distance-colouring of graphs
• A unified approach to distance-two colouring of graphs on surfaces
• Coloring Powers of Planar Graphs
• Coloring with no 2-colored \(P_4\)'s
• Colouring and covering nowhere dense graphs
• Colouring graphs with bounded generalized colouring number
• Competitive colorings of oriented graphs
• Efficient graph packing via game colouring
• Grad and classes with bounded expansion. I: Decompositions
• Graphs on surfaces
• Graphs with linearly bounded Ramsey numbers
• Models and approximation algorithms for channel assignment in radio networks
• On low tree-depth decompositions
• On the generalised colouring numbers of graphs that exclude a fixed minor
• Orderings on graphs and game coloring number
• Radius two trees specify χ‐bounded classes
• Refined activation strategy for the marking game
• Sparsity. Graphs, structures, and algorithms
• Tree-depth, subgraph coloring and homomorphism bounds
• Walk-powers and homomorphism bounds of planar signed graphs

Cited in

(20)

• Improved bounds for weak coloring numbers
• Exact square coloring of certain classes of graphs: complexity and algorithms
• On the weak 2-coloring number of planar graphs
• Colouring graphs with bounded generalized colouring number
• ON DISTANCES IN CHROMATIC GRAPHS
• 2-distance, injective, and exact square list-coloring of planar graphs with maximum degree 4
• On coloring numbers of graph powers
• scientific article; zbMATH DE number 4118392 (Why is no real title available?)
• Exact distance graphs of product graphs
• Dimension is polynomial in height for posets with planar cover graphs
• scientific article; zbMATH DE number 57114 (Why is no real title available?)
• On chromatic numbers of nearly Kneser distance graphs
• Exact distance colouring in trees
• Two lower bounds for \(p\)-centered colorings
• Colouring exact distance graphs of chordal graphs
• scientific article; zbMATH DE number 3968609 (Why is no real title available?)
• Exact square coloring of subcubic planar graphs
• Total difference chromatic numbers of graphs
• The clique number of the exact distance \(t\)-power graph: complexity and eigenvalue bounds
• Injective coloring of graphs revisited

This page was built for publication: Chromatic numbers of exact distance graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1633747)