IJPAM: Volume 85, No. 1 (2013)


Kristína Budajová1, Július Czap2
1Department of Aerodynamics and Simulations
Faculty of Aeronautics
Technical University of Košice
Rampová 7, SK-041 21 Košice, SLOVAKIA
2Department of Applied Mathematics and Business Informatics
Faculty of Economics
Technical University of Košice
B. Němcovej 32, SK-040 01 Košice, SLOVAKIA

Abstract. An edge-coloring of a 2-connected plane graph G is a r-acyclic edge-coloring if every facial cycle C in G is colored with at least min{|C|,r} colors, in addition, no two face-adjacent edges (consecutive edges of a facial trail of some face) receive the same color. The minimum number of colors used in such a coloring of G is denoted by afr'(G)

In this paper, we determine tight upper bounds for afr'(G).

Received: February 1, 2013

AMS Subject Classification: 05C10, 05C15

Key Words and Phrases: plane graph, facial cycle, edge-coloring

Download paper from here.

DOI: 10.12732/ijpam.v85i1.11 How to cite this paper?
International Journal of Pure and Applied Mathematics
ISSN printed version: 1311-8080
ISSN on-line version: 1314-3395
Year: 2013
Volume: 85
Issue: 1