Tree-like distance colouring for planar graphs of sufficient girth

MaRDI QIDQ668079zbMATH OpenFDO

Authors Ross J. Kang, Willem van Loon

Publication date 5 March 2019

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1805.02156, https://www.combinatorics.org/ojs/index.php/eljc/article/view/v26i1p23

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15) Extremal problems in graph theory (05C35)

Abstract: Given a multigraph $G$ and a positive integer $t$, the distance-$t$ chromatic index of $G$ is the least number of colours needed for a colouring of the edges so that every pair of distinct edges connected by a path of fewer than $t$ edges must receive different colours. Let $pi{\text{'}}_t(d)$ and $au{\text{'}}_t(d)$ be the largest values of this parameter over the class of planar multigraphs and of (simple) trees, respectively, of maximum degree $d$. We have that $pi{\text{'}}_t(d)$ is at most and at least a non-trivial constant multiple larger than $au{\text{'}}_t(d)$. (We conjecture $limsu{p}_{doinfty}pi{\text{'}}_2(d)/au{\text{'}}_2(d)=9/4$ in particular.) We prove for odd $t$ the existence of a quantity $g$ depending only on $t$ such that the distance-$t$ chromatic index of any planar multigraph of maximum degree $d$ and girth at least $g$ is at most $au{\text{'}}_t(d)$ if $d$ is sufficiently large. Such a quantity does not exist for even $t$. We also show a related, similar phenomenon for distance vertex-colouring.

Review text

Summary: Given a multigraph \(G\) and a positive integer \(t\), the distance-\(t\) chromatic index of \(G\) is the least number of colours needed for a colouring of the edges so that every pair of distinct edges connected by a path of fewer than \(t\) edges must receive different colours. Let \(\pi'_t(d)\) and \(\tau'_t(d)\) be the largest values of this parameter over the class of planar multigraphs and of (simple) trees, respectively, of maximum degree \(d\). We have that \(\pi'_t(d)\) is at most and at least a non-trivial constant multiple larger than \(\tau'_t(d)\). (We conjecture \(\limsup_{d\rightarrow\infty}\pi'_2(d)/\tau'_2(d) =9/4\) in particular.) We prove for odd \(t\) the existence of a quantity \(g\) depending only on \(t\) such that the distance-\(t\) chromatic index of any planar multigraph of maximum degree \(d\) and girth at least \(g\) is at most \(\tau'_t(d)\) if \(d\) is sufficiently large. Such a quantity does not exist for even \(t\). We also show a related, similar phenomenon for distance vertex-colouring.

Recommendations

• The distance-t chromatic index of graphs
• 2-distance coloring of planar graphs with girth 5
• 2-distance coloring of sparse planar graphs
• Exact distance colouring in trees
• Some maximum multigraphs and adge/vertex distance colourings

Cites work

• A bound on the strong chromatic index of a graph
• A Theorem on Coloring the Lines of a Network
• Coloring Powers of Planar Graphs
• Colouring squares of claw-free graphs
• Constructions of large planar networks with given degree and diameter
• Every planar map is four colorable. I: Discharging
• Every planar map is four colorable. II: Reducibility
• Graph theory
• scientific article; zbMATH DE number 3265667 (Why is no real title available?)
• scientific article; zbMATH DE number 3273761 (Why is no real title available?)
• scientific article; zbMATH DE number 4187830 (Why is no real title available?)
• List Colouring Squares of Planar Graphs
• Local structures in plane maps and distance colourings
• Optimal approximation of sparse hessians and its equivalence to a graph coloring problem
• Parameters of two-prover-one-round game and the hardness of connectivity problems
• Planar graphs of maximum degree seven are Class I
• Precise upper bound for the strong edge chromatic number of sparse planar graphs
• Strong chromatic index of planar graphs with large girth
• Strong chromatic index of subcubic planar multigraphs
• Sufficient conditions for planar graphs to be 2-distance (\(\Delta+1\))-colourable

Cited in

(6)

• Distance colouring without one cycle length
• Colouring exact distance graphs of chordal graphs
• Distance colouring without one cycle length
• Exact distance colouring in trees
• The distance-t chromatic index of graphs
• Strong chromatic index and Hadwiger number

This page was built for publication: Tree-like distance colouring for planar graphs of sufficient girth

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