Colouring exact distance graphs of chordal graphs

DOI10.1016/J.DISC.2019.111769MaRDI QIDQ2305897zbMATH OpenOpenAlexFDO

Authors Daniel A. Quiroz

Publication date 20 March 2020

Published in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

adjacent-cliques graphchordal graphexact distance graphgenusisometric subgraphtree-width

Mathematics Subject Classification ID

Distance in graphs (05C12) Coloring of graphs and hypergraphs (05C15) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Abstract: For a graph $G=(V,E)$ and positive integer $p$, the exact distance-$p$ graph $G^{[aturalp]}$ is the graph with vertex set $V$ and with an edge between vertices $x$ and $y$ if and only if $x$ and $y$ have distance $p$. Recently, there has been an effort to obtain bounds on the chromatic number $chi(G^{[aturalp]})$ of exact distance-$p$ graphs for $G$ from certain classes of graphs. In particular, if a graph $G$ has tree-width $t$, it has been shown that $chi(G^{[aturalp]})inmathcalO(p^{t-1})$ for odd $p$, and $chi(G^{[aturalp]})inmathcalO(p^{t}Delta(G))$ for even $p$. We show that if $G$ is chordal and has tree-width $t$, then $chi(G^{[aturalp]})inmathcalO(p,t^2)$ for odd $p$, and $chi(G^{[aturalp]})inmathcalO(p,t^{2}Delta(G))$ for even $p$. If we could show that for every graph $H$ of tree-width $t$ there is a chordal graph $G$ of tree-width $t$ which contains $H$ as an isometric subgraph (i.e., a distance preserving subgraph), then our results would extend to all graphs of tree-width $t$. While we cannot do this, we show that for every graph $H$ of genus $g$ there is a graph $G$ which is a triangulation of genus $g$ and contains $H$ as an isometric subgraph.

Recommendations

• Chromatic numbers of exact distance graphs
• Exact distance colouring in trees
• On powers of chordal graphs and their colorings
• scientific article; zbMATH DE number 3968609
• Tree-like distance colouring for planar graphs of sufficient girth

Cites work

• Chromatic numbers of exact distance graphs
• Coloring Powers of Chordal Graphs
• Coloring Powers of Planar Graphs
• Embedding graphs as isometric medians
• Exact distance colouring in trees
• scientific article; zbMATH DE number 3834023 (Why is no real title available?)
• scientific article; zbMATH DE number 3641484 (Why is no real title available?)
• scientific article; zbMATH DE number 3265667 (Why is no real title available?)
• scientific article; zbMATH DE number 3308991 (Why is no real title available?)
• Incidence matrices and interval graphs
• Induced subgraphs of graphs with large chromatic number. I. Odd holes
• Nonrepetitive colorings of graphs of bounded tree-width
• On low tree-depth decompositions
• On rigid circuit graphs
• Sparsity. Graphs, structures, and algorithms
• The strong chromatic index of sparse graphs

Cited in

(9)

• Chromatic numbers of exact distance graphs
• Exact square coloring of certain classes of graphs: complexity and algorithms
• Exact square coloring of subcubic planar graphs
• Integral-root polynomials and chromatic uniqueness of graphs
• Exact distance colouring in trees
• 2-distance, injective, and exact square list-coloring of planar graphs with maximum degree 4
• Chromatic coloring of distance graphs, III
• The clique number of the exact distance t-power graph: complexity and eigenvalue bounds
• Fast algorithm for S-packing coloring of Halin graphs

This page was built for publication: Colouring exact distance graphs of chordal graphs

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