Chromatic numbers of exact distance graphs

DOI10.1016/J.JCTB.2018.05.007zbMATH Open1402.05084arXiv1612.02160OpenAlexW2963893440MaRDI QIDQ1633747FDOQ1633747

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)

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.

Full work available at URL: https://arxiv.org/abs/1612.02160

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

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)

Cites Work

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