Distance colouring without one cycle length

DOI10.1016/J.ENDM.2017.07.025MaRDI QIDQ1689995zbMATH OpenOpenAlexFDO

Authors Ross J. Kang, François Pirot

Publication date 18 January 2018

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

zbMATH Keywords

graph colouringgraph powersdistance colouringexcluded cycles

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Paths and cycles (05C38)

Abstract: We consider distance colourings in graphs of maximum degree at most $d$ and how excluding one fixed cycle length $ell$ affects the number of colours required as $doinfty$. For vertex-colouring and $tge1$, if any two distinct vertices connected by a path of at most $t$ edges are required to be coloured differently, then a reduction by a logarithmic (in $d$) factor against the trivial bound $O(d^t)$ can be obtained by excluding an odd cycle length $ellge3t$ if $t$ is odd or by excluding an even cycle length $ellge2t+2$. For edge-colouring and $tge2$, if any two distinct edges connected by a path of fewer than $t$ edges are required to be coloured differently, then excluding an even cycle length $ellge2t$ is sufficient for a logarithmic factor reduction. For $tge2$, neither of the above statements are possible for other parity combinations of $ell$ and $t$. These results can be considered extensions of results due to Johansson (1996) and Mahdian (2000), and are related to open problems of Alon and Mohar (2002) and Kaiser and Kang (2014).

Recommendations

• Distance colouring without one cycle length
• The distance-\(t\) chromatic index of graphs
• Tree-like distance colouring for planar graphs of sufficient girth
• 2-Distance coloring of planar graphs without short cycles

Cites work

• scientific article; zbMATH DE number 3652373 (Why is no real title available?)
• scientific article; zbMATH DE number 3284071 (Why is no real title available?)
• A General Upper Bound on the List Chromatic Number of Locally Sparse Graphs
• A note on the Turán function of even cycles
• Coloring graphs with sparse neighborhoods
• Coloring powers and girth
• Cycles of even length in graphs
• Problems and results in combinatorial analysis and graph theory
• The Chromatic Number of Graph Powers
• The distance-\(t\) chromatic index of graphs
• The strong chromatic index ofC4-free graphs

Cited in

(1)

• Distance colouring without one cycle length

This page was built for publication: Distance colouring without one cycle length

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