On incidence coloring conjecture in Cartesian products of graphs

DOI10.1016/J.DAM.2016.04.030zbMATH Open1344.05117arXiv1505.04908OpenAlexW2355202049WikidataQ123191967 ScholiaQ123191967MaRDI QIDQ313802FDOQ313802

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

Publication date: 12 September 2016

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

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.

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)

Cites Work

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

Cited In (9)

• On incidence choosability of cubic graphs
• Incidence choosability of graphs
• Note on incidence chromatic number of subquartic graphs
• Incidence coloring of mycielskians with fast algorithm
• Title not available (Why is that?)
• Hypergraph incidence coloring
• Strong incidence coloring of outerplanar graphs
• On incidence coloring of graph fractional powers
• Title not available (Why is that?)

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)