On incidence coloring conjecture in Cartesian products of graphs

DOI10.1016/J.DAM.2016.04.030MaRDI QIDQ313802zbMATH OpenOpenAlexWikidataFDO

Authors Petr Gregor, Borut Lužar, Roman Soták

Publication date 12 September 2016

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1505.04908

zbMATH Keywords

Cartesian productincidence coloringlocally injective homomorphism

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph operations (line graphs, products, etc.) (05C76)

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)$ $vuine,f$. An incidence coloring of $G$ is a coloring of its incidences assigning distinct colors to adjacent incidences. It was conjectured that at most $Delta(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 $Delta(G)+2$ colors.

Recommendations

• Incidence coloring of Cartesian product graphs
• The incidence chromatic number and the adjacent vertex distinguishing incidence chromatic number of the Cartesian product
• scientific article; zbMATH DE number 6001818
• Incidence coloring of mycielskians with fast algorithm
• Incidence coloring -- cold cases

Cites work

• scientific article; zbMATH DE number 3577144 (Why is no real title available?)
• 2-distance coloring of sparse graphs
• Incidence and strong edge colorings of graphs
• Incidence coloring of Cartesian product graphs
• Incidence coloring of \(k\)-degenerated graphs
• Incidence coloring of regular graphs and complement graphs
• Incidence coloring on hypercubes
• Incidence colorings of the powers of cycles
• Invalid proofs on incidence coloring
• Locally constrained graph homomorphisms -- structure, complexity, and applications
• On incidence coloring and star arboricity of graphs
• The incidence chromatic number of toroidal grids
• The incidence coloring conjecture for graphs of maximum degree 3
• The incidence coloring number of Halin graphs and outerplanar graphs
• The incidence coloring numbers of meshes
• The star arboricity of graphs

Cited in

(12)

• scientific article; zbMATH DE number 7594570 (Why is no real title available?)
• Incidence coloring of mycielskians with fast algorithm
• Hypergraph incidence coloring
• Strong incidence coloring of outerplanar graphs
• The incidence chromatic number of toroidal grids
• The incidence chromatic number and the adjacent vertex distinguishing incidence chromatic number of the Cartesian product
• Note on incidence chromatic number of subquartic graphs
• Simultaneous coloring of vertices and incidences of hypercubes
• On incidence coloring of graph fractional powers
• Incidence choosability of graphs
• On incidence choosability of cubic graphs
• Incidence coloring of Cartesian product graphs

This page was built for publication: On incidence coloring conjecture in Cartesian products of graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q313802)