2-edge-colored chromatic number of grids is at most 9

DOI10.1007/S00373-020-02155-YMaRDI QIDQ2175809zbMATH OpenOpenAlexFDO

Authors Janusz Dybizbański

Publication date 30 April 2020

Published in Graphs and Combinatorics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

2-edge-colored coloringgridsPaley graphs

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Abstract: A signified graph is a pair $(G,Sigma)$ where $G$ is a graph, and $Sigma$ is a set of edges marked with '$-$'. Other edges are marked with '$+$'. A signified coloring of the signified graph $(G,Sigma)$ is a homomorphism into a signified graph $(H,Delta)$. The signified chromatic number of the signified graph $(G,Sigma)$ is the minimum order of $H$. In this paper we show that for every 2-dimensional grid $(G,Sigma)$ there exists homomorphism from $(G,Sigma)$ into the signed Paley graphs $S{P}_9$. Hence signified chromatic number of the signified grids is at most 9. This improves upper bound on this number obtained recently by Bensmail.

Review text

A 2-edge-colored graph is a pair \((G,\sigma)\), where \(G\) is an undirected graph and \(\sigma:E(G)\to \{-, +\}\) is a function assigning a sign to each of the edges. A 2-edge-colored coloring of a 2-edge-colored graph \((G,\sigma)\) is a proper coloring \(\phi\) of \(V(G)\) such that if there exist edges \(\{u,v\}\) and \(\{x,y\}\) with \(\phi(u)=\phi(x)\) and \(\phi(v)=\phi(y)\), then \(\{u,v\}\) and \(\{x,y\}\) have the same sign. The 2-edge-colored chromatic number of the 2-edge-colored graph \((G,\sigma)\) is the minimum number of colors required for a 2-edge-colored coloring. The 2-edge-colored chromatic number of a graph \(G\), denoted by \(\chi_2(G)\), is the maximum over all 2-edge-colored of \(G\). Given a graph class \(\mathcal{F}\), the 2-edge-colored chromatic number \(\chi_2(\mathcal{F})\) is the maximum of the 2-edge-colored chromatic numbers of the elements in \(\mathcal{F}\). This paper deals with the 2-edge-colored chromatic number for the class of 2-dimensional grids \(\mathcal{G}\), where a grid is the Cartesian product of two paths. The author shows that \(8\leq\chi_2(\mathcal{G})\leq 9\) and \(7\leq\chi_2(\mathcal{G}_3)\leq 8\) for the class \(\mathcal{G}_3\) of grids with 3 columns. These results improve the bounds in [\textit{J. Bensmail}, Aust. J. Combin. 75, No. 3, 365--384 (2019; Zbl 1429.05059)].

Recommendations

• On the 2-edge-coloured chromatic number of grids
• scientific article; zbMATH DE number 6453552
• Acyclic and \(k\)-distance coloring of the grid
• Signed coloring of 2-dimensional grids
• The total chromatic number of some bipartite graphs
• Adjacent vertex-distinguishing edge colorings of a class of two dimensional generalized grid graphs generated by complete graphs
• The total chromatic number of some bipartite graphs.
• Adjacent vertex-distinguishing total colorings of a class of two dimensional generalized grid graphs
• Upper bounds for the 2-hued chromatic number of graphs in terms of the independence number
• scientific article; zbMATH DE number 5942282

Cites work

• A note on the oriented chromatic number of grids
• Analogues of cliques for \((m,n)\)-colored mixed graphs
• Homomorphisms and colourings of oriented graphs: an updated survey
• Homomorphisms of 2-edge-colored graphs
• Homomorphisms of 2-edge-colored triangle-free planar graphs
• scientific article; zbMATH DE number 3194323 (Why is no real title available?)
• On the 2-edge-coloured chromatic number of grids
• On the oriented chromatic number of grids
• Oriented chromatic number of grids is greater than 7

Cited in

(5)

• On the chromatic numbers of signed triangular and hexagonal grids
• On the pushable chromatic number of various types of grids
• scientific article; zbMATH DE number 5717258 (Why is no real title available?)
• On the 2-edge-coloured chromatic number of grids
• The chromatic number of 2-edge-colored and signed graphs of bounded maximum degree

This page was built for publication: 2-edge-colored chromatic number of grids is at most 9

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