Edge-coloring of plane multigraphs with many colors on facial cycles

Autor:	Stanislav Jendrol, Juraj Valiska, Július Czap
Rok vydání:	2020
Předmět:	Plane (geometry) Applied Mathematics Arboricity Multigraph Planar graph Combinatorics symbols.namesake Edge coloring Integer symbols Discrete Mathematics and Combinatorics Acyclic coloring Constant (mathematics) Mathematics
Zdroj:	Discrete Applied Mathematics. 282:80-85
ISSN:	0166-218X
DOI:	10.1016/j.dam.2019.11.003
Popis:	For a fixed positive integer p , a coloring of the edges of a multigraph G is called p -acyclic coloring if every cycle C in G contains at least min { | C | , p + 1 } colors. The least number of colors needed for a p -acyclic coloring of G is the p -arboricity of G . From a result of Bartnicki et al. (2019) it follows that there are planar graphs with unbounded p -arboricity. In this note we relax the definition of p -arboricity for plane multigraphs in sense that the requirement is not for all cycles but only for facial cycles and show that the smallest number of colors needed for such a coloring is a constant (depending on p only).
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::cd2b0c1b39fa2ee89b52454f90e18694 https://doi.org/10.1016/j.dam.2019.11.003 Zobrazit plný text záznamu Full Text from ScienceDirect