Tree-like distance colouring for planar graphs of sufficient girth

zbMATH Open1409.05087arXiv1805.02156MaRDI QIDQ668079FDOQ668079

Authors: Ross J. Kang, Willem van Loon 

Publication date: 5 March 2019

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

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.

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

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

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

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (6)

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

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)