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

gridsPaley graphs2-edge-colored coloring

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.

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

• scientific article; zbMATH DE number 3194323 (Why is no real title available?)
• 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
• 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)

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

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)