Abstract | ||
---|---|---|
An incidence in a graph G is a pair ( v , e ) where v is a vertex of G and e is an edge of G incident to v . Two incidences ( v , e ) and ( u , f ) are adjacent if at least one of the following holds: ( a ) v = u , ( b ) e = f , or ( c ) v u ź { e , f } . An incidence coloring of G is a coloring of its incidences assigning distinct colors to adjacent incidences. It was conjectured that at most Δ ( G ) + 2 colors are needed for an incidence coloring of any graph G . The conjecture is false in general, but the bound holds for many classes of graphs. We introduce some sufficient properties of the two factor graphs of a Cartesian product graph G for which G admits an incidence coloring with at most Δ ( G ) + 2 colors. |
Year | DOI | Venue |
---|---|---|
2016 | 10.1016/j.dam.2016.04.030 | Discrete Applied Mathematics |
Keywords | Field | DocType |
Incidence coloring,Cartesian product,Locally injective homomorphism | Complete coloring,Discrete mathematics,Combinatorics,Vertex (geometry),Fractional coloring,Bound graph,Cartesian product,List coloring,Brooks' theorem,Mathematics,Graph coloring | Journal |
Volume | Issue | ISSN |
213 | C | 0166-218X |
Citations | PageRank | References |
2 | 0.41 | 10 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Petr Gregor | 1 | 178 | 19.79 |
Borut Luzar | 2 | 42 | 10.86 |
Roman Soták | 3 | 128 | 24.06 |