2015/05/19 by Petr Gregor, Gregor, Petr, Borut Lužar +3
Computer Science · Engineering · #05C15 #05C76 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.1505.04908
openalex publication_date 2015/05/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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) vu ∈ \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.