On the pushable chromatic number of various types of grids

DOI10.1016/J.DAM.2023.01.013MaRDI QIDQ2686138zbMATH OpenOpenAlexFDO

Authors Julien Bensmail, Dimitri Lajou, Soumen Nandi, Sagnik Sen, Tapas K. Das

Publication date 24 February 2023

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

Full work available at URL https://doi.org/10.1016/j.dam.2023.01.013

zbMATH Keywords

gridoriented colouringoriented graphpushable chromatic number

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Small world graphs, complex networks (graph-theoretic aspects) (05C82)

Recommendations

• Pushable chromatic number of graphs with degree constraints
• Pushable chromatic number of graphs with maximum average degree at most \(\frac{14}{5}\)
• On the 2-edge-coloured chromatic number of grids
• On homomorphisms of oriented graphs with respect to the push operation
• Homomorphisms and oriented colorings of equivalence classes of oriented graphs

Cites work

• 2-edge-colored chromatic number of grids is at most 9
• Analogues of cliques for \((m,n)\)-colored mixed graphs
• Complexity dichotomy for oriented homomorphism of planar graphs with large girth
• Hamiltonicity and reversing arcs in digraphs
• Homomorphisms and colourings of oriented graphs: an updated survey
• Homomorphisms and oriented colorings of equivalence classes of oriented graphs
• Homomorphisms of signed graphs
• Homomorphisms of signed graphs: an update
• On homomorphisms of oriented graphs with respect to the push operation
• On oriented cliques with respect to push operation
• On reorienting graphs by pushing down maximal vertices
• On the 2-edge-coloured chromatic number of grids
• On the chromatic numbers of signed triangular and hexagonal grids
• On the maximum average degree and the oriented chromatic number of a graph
• On the oriented chromatic number of grids
• Oriented chromatic number of grids is greater than 7
• Oriented cliques and colorings of graphs with low maximum degree
• Oriented, 2-edge-colored, and 2-vertex-colored homomorphisms
• Pushable chromatic number of graphs with degree constraints
• Pushing vertices and orienting edges
• Re-orienting tournaments by pushing vertices.
• Signed coloring of 2-dimensional grids

Cited in

(8)

• On the oriented chromatic number of grids
• Pushable chromatic number of graphs with degree constraints
• On the chromatic numbers of signed triangular and hexagonal grids
• Grid representations and the chromatic number
• Pushable chromatic number of graphs with maximum average degree at most \(\frac{14}{5}\)
• The oriented chromatic number of the hexagonal grid is 6
• Pushing cops and robber on graphs of maximum degree four
• An update on pushable homomorphisms

This page was built for publication: On the pushable chromatic number of various types of grids

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