On the chromatic numbers of signed triangular and hexagonal grids

DOI10.1016/J.IPL.2021.106156MaRDI QIDQ2234782zbMATH OpenOpenAlexFDO

Authors Fabien Jacques

Publication date 19 October 2021

Published in Information Processing Letters (Search for Journal in Brave)

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

zbMATH Keywords

chromatic numbercombinatorial problemshomomorphismssigned graphs

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Signed and weighted graphs (05C22)

Abstract: A signed graph is a simple graph with two types of edges. Switching a vertex $v$ of a signed graph corresponds to changing the type of each edge incident to $v$. A homomorphism from a signed graph $G$ to another signed graph $H$ is a mapping $varphi:V(G)ightarrowV(H)$ such that, after switching any number of the vertices of $G$, $varphi$ maps every edge of $G$ to an edge of the same type in $H$. The chromatic number $ch{i}_s(G)$ of a signed graph $G$ is the order of a smallest signed graph $H$ such that there is a homomorphism from $G$ to $H$. We show that the chromatic number of signed triangular grids is at most 10 and the chromatic number of signed hexagonal grids is at most 4.

Review text

A signed graph \(G\) consists of a graph \(G = (V,E)\) together with a signature (considered as an edge 2-coloring) \(s: E(G) \to \{1, -1\}\). A homomorphism from a signed graph \(G\) to a signed graph \(H\) is a mapping \(\phi: V(G) \to V(H)\) such that, after performing switching operations at a subset of vertices in \(V(G)\), every edge of \(G\) is mapped to an edge of \(H\) with the same sign. The chromatic number \(\chi_s(G)\) of a signed graph \(G\), is the order of a smallest signed graph \(H\) such that there exists a homomorphism from \(G\) to \(H\). It is shown that the chromatic number of a signed hexagonal grid is 4 and the chromatic number of a signed triangular grid is at most 10. At the end of the paper, an interesting conjectured is posed that the chromatic number of a signed triangular grid equals 6.

Recommendations

• On the oriented chromatic number of grids
• Grid representations and the chromatic number
• A note on the oriented chromatic number of grids
• On the pushable chromatic number of various types of grids
• On periodicity of perfect colorings of the infinite hexagonal and triangular grids
• On the 2-edge-coloured chromatic number of grids
• Chromatic number and orientations of graphs and signed graphs
• Grid drawings and the chromatic number
• On the packing chromatic number of square and hexagonal lattice
• On the signed chromatic number of some classes of graphs

Cites work

• 2-edge-colored chromatic number of grids is at most 9
• Classification of edge-critical underlying absolute planar cliques for signed graphs
• Edge-switching homomorphisms of edge-coloured graphs
• Homomorphisms of 2-edge-colored graphs
• Homomorphisms of 2-edge-colored triangle-free planar graphs
• Homomorphisms of signed graphs
• Homomorphisms of signed graphs: an update
• Pushable chromatic number of graphs with degree constraints
• Signed coloring of 2-dimensional grids
• Signed graphs

Cited in

(9)

• The chromatic number of signed graphs with bounded maximum average degree
• Signed coloring of 2-dimensional grids
• Grid representations and the chromatic number
• On the signed chromatic number of some classes of graphs
• On the pushable chromatic number of various types of grids
• scientific article; zbMATH DE number 6002424 (Why is no real title available?)
• On periodicity of perfect colorings of the infinite hexagonal and triangular grids
• The chromatic number of 2-edge-colored and signed graphs of bounded maximum degree
• An update on pushable homomorphisms

This page was built for publication: On the chromatic numbers of signed triangular and hexagonal grids

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