Name
Abstract | ||
|---|---|---|
An acyclic edge coloring of a graph is a proper edge coloring without bichromatic cycles. In 1978, it was conjectured that @D(G)+2 colors suffice for an acyclic edge coloring of every graph G (Fiamcik, 1978 [8]). The conjecture has been verified for several classes of graphs, however, the best known upper bound for as special class as planar graphs are, is @D+12 (Basavaraju and Chandran, 2009 [3]). In this paper, we study simple planar graphs which need only @D(G) colors for an acyclic edge coloring. We show that a planar graph with girth g and maximum degree @D admits such acyclic edge coloring if g=12, or g=8 and @D=4, or g=7 and @D=5, or g=6 and @D=6, or g=5 and @D=10. Our results improve some previously known bounds. |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1016/j.dam.2012.01.017 | Discrete Applied Mathematics |
Keywords | Field | DocType |
bichromatic cycle,maximum degree,acyclic edge coloring,colors suffice,acyclic edge,planar graph,graph g,girth g,simple planar graph,proper edge | Discrete mathematics,Edge coloring,Complete coloring,Combinatorics,Fractional coloring,List coloring,Nowhere-zero flow,Brooks' theorem,Greedy coloring,Mathematics,Graph coloring | Journal |
Volume | Issue | ISSN |
160 | 9 | 0166-218X |
Citations | PageRank | References |
3 | 0.43 | 8 |
Authors | ||
5 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Dávid Hudák | 1 | 51 | 4.81 |
| František Kardoš | 2 | 87 | 9.72 |
| Borut Luar | 3 | 12 | 1.08 |
| Roman Soták | 4 | 128 | 24.06 |
| Riste Škrekovski | 5 | 607 | 83.39 |