-facial edge colorings of graphs

DOI10.1016/J.DAM.2014.10.009MaRDI QIDQ479043zbMATH OpenOpenAlexFDO

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)

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

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)

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.

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

Cites work

• scientific article; zbMATH DE number 3735847 (Why is no real title available?)
• 3-Facial Coloring of Plane Graphs
• A note on 2-facial coloring of plane graphs
• Cyclic, diagonal and facial colorings
• Cyclic, diagonal and facial colorings -- a missing case
• Facial colorings using Hall's theorem

Cited in

(19)

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

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)