Strong edge-coloring of cubic bipartite graphs: a counterexample

DOI10.1016/J.DAM.2022.07.008MaRDI QIDQ2172406zbMATH OpenOpenAlexWikidataFDO

Authors Daniel W. Cranston

Publication date 15 September 2022

Published in Discrete Applied Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

counterexamplecubicstrong edge-coloring

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Abstract: A strong edge-coloring $varphi$ of a graph $G$ assigns colors to edges of $G$ such that $varphi(e_1)evarphi(e_2)$ whenever $e_1$ and $e_2$ are at distance no more than 1. It is equivalent to a proper vertex coloring of the square of the line graph of $G$. In 1990 Faudree, Schelp, Gy'arf'as, and Tuza conjectured that if $G$ is a bipartite graph with maximum degree 3 and sufficiently large girth, then $G$ has a strong edge-coloring with at most 5 colors. In 2021 this conjecture was disproved by Luv{z}ar, Mav{c}ajov'{a}, v{S}koviera, and Sot'{a}k. Here we give an alternative construction to disprove the conjecture.

Recommendations

• Strong edge-coloring of \((3, \varDelta)\)-bipartite graphs
• A note on the strong chromatic index of bipartite graphs
• The strong chromatic index of \((3,\Delta)\)-bipartite graphs
• Strong edge coloring sparse graphs
• Strong edge colorings of graphs

Cites work

• scientific article; zbMATH DE number 3882451 (Why is no real title available?)
• scientific article; zbMATH DE number 3851125 (Why is no real title available?)
• scientific article; zbMATH DE number 3189017 (Why is no real title available?)
• scientific article; zbMATH DE number 4187830 (Why is no real title available?)
• Induced matchings in cubic graphs
• On induced matchings
• Recent progress on strong edge-coloring of graphs
• Regular Graphs with Given Girth and Restricted Circuits
• Strong chromatic index of subcubic planar multigraphs
• The strong chromatic index of a class of graphs
• The strong chromatic index of a cubic graph is at most 10

Cited in

(5)

• Θ-graphs of partial cubes and strong edge colorings
• Strong edge-coloring of \((3, \varDelta)\)-bipartite graphs
• The strong chromatic index of \((3,\Delta)\)-bipartite graphs
• On strong edge-coloring of graphs with maximum degree 5
• Graphs and hypergraphs of prescribed girth and degrees with restricted cycles

This page was built for publication: Strong edge-coloring of cubic bipartite graphs: a counterexample

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