-facial edge colorings of graphs

DOI10.1016/J.DAM.2014.10.009zbMATH Open1304.05050arXiv1303.4346OpenAlexW2034174803MaRDI QIDQ479043FDOQ479043

Authors: Borut Lužar, Martina Mockovčiaková, Roman Soták, Riste Škrekovski, Peter Šugerek 

Publication date: 5 December 2014

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

Abstract: An l-facial edge coloring of a plane graph is a coloring of the edges such that any two edges at distance at most l on a boundary walk of some face receive distinct colors. It is conjectured that 3l + 1 colors suffice for an l-facial edge coloring of any plane graph. We prove that 7 colors suffice for a 2-facial edge coloring of any plane graph and therefore confirm the conjecture for l = 2.

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

Recommendations

• 3-facial edge-coloring of plane graphs
• 3-Facial Coloring of Plane Graphs
• Facial parity edge colouring
• Facial colorings using Hall's theorem
• A note on 2-facial coloring of plane graphs

zbMATH Keywords

plane graphfacial coloring\(\ell\)-facial edge coloring

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Distance in graphs (05C12) Coloring of graphs and hypergraphs (05C15)

Cites Work

• Title not available (Why is that?)
• Cyclic, diagonal and facial colorings
• Cyclic, diagonal and facial colorings -- a missing case
• 3-Facial Coloring of Plane Graphs
• Facial colorings using Hall's theorem
• A note on 2-facial coloring of plane graphs

Cited In (19)

• Facial incidence colorings of embedded multigraphs
• A survey on the cyclic coloring and its relaxations
• 3-Facial Coloring of Plane Graphs
• Facial rainbow edge-coloring of plane graphs
• Facial \([r,s,t]\)-colorings of plane graphs
• On \(d\)-diagonal colorings of embedded graphs of low maximum face size
• Facially-constrained colorings of plane graphs: a survey
• Facial packing edge-coloring of plane graphs
• Title not available (Why is that?)
• Facial \(L(2, 1)\)-edge-labelings of trees
• Facial colorings using Hall's theorem
• Facial edge-face coloring of \(K_4\)-minor-free graphs
• Facial visibility in edge colored plane graphs
• A note on 2-facial coloring of plane graphs
• Facial edge ranking of plane graphs
• 3-facial edge-coloring of plane graphs
• Cyclic, diagonal and facial colorings
• Facial parity edge coloring of outerplane graphs
• Improved bound on facial parity edge coloring

This page was built for publication: \(\ell\)-facial edge colorings of graphs

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