Back to Search
Start Over
Strong Edge-Coloring of Cubic Bipartite Graphs: A Counterexample
- Source :
- Discrete Applied Math. Volume 321, 15 November 2022, pp. 258-260
- Publication Year :
- 2021
-
Abstract
- A strong edge-coloring $\varphi$ of a graph $G$ assigns colors to edges of $G$ such that $\varphi(e_1)\ne \varphi(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 Lu\v{z}ar, Ma\v{c}ajov\'{a}, \v{S}koviera, and Sot\'{a}k. Here we give an alternative construction to disprove the conjecture.<br />Comment: 3.5 pages, 1 figure; second version extends the construction from the 3-regular case to the $k$-regular case, for each integer $k\ge 2$; third version incorporates referee feedback; to appear in Discrete Applied Math
- Subjects :
- Mathematics - Combinatorics
05C15
Subjects
Details
- Database :
- arXiv
- Journal :
- Discrete Applied Math. Volume 321, 15 November 2022, pp. 258-260
- Publication Type :
- Report
- Accession number :
- edsarx.2112.01443
- Document Type :
- Working Paper