Pushable chromatic number of graphs with degree constraints

DOI10.1016/j.disc.2020.112151zbMath1459.05072arXiv1911.09909OpenAlexW3082538292MaRDI QIDQ2219941

Julien Bensmail, Théo Pierron, Soumyajit Paul, Sandip Das, Sagnik Sen, Soumen Nandi, Eric Sopena

Publication date: 21 January 2021

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

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

zbMATH Keywords

graph homomorphismmaximum degreesubcubic graphoriented coloringpush operation

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Directed graphs (digraphs), tournaments (05C20) Vertex degrees (05C07) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items (5)

On the pushable chromatic number of various types of grids ⋮ Pushable chromatic number of graphs with maximum average degree at most \(\frac{14}{5}\) ⋮ The chromatic number of 2-edge-colored and signed graphs of bounded maximum degree ⋮ A homomorphic polynomial for oriented graphs ⋮ On the chromatic numbers of signed triangular and hexagonal grids

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Homomorphisms and colourings of oriented graphs: an updated survey
• On graphs that can be oriented as diagrams of ordered sets
• On reorienting graphs by pushing down maximal vertices
• The monadic second order logic of graphs. VI: On several representations of graphs by relational structures
• Homomorphisms and oriented colorings of equivalence classes of oriented graphs
• Oriented colourings of graphs with maximum degree three and four
• Complexity dichotomy for oriented homomorphism of planar graphs with large girth
• On homomorphisms of oriented graphs with respect to the push operation
• On oriented cliques with respect to push operation
• Acyclic and oriented chromatic numbers of graphs
• Hamiltonicity and reversing arcs in digraphs
• Tournament games and positive tournaments
• Homomorphism bounds for oriented planar graphs

This page was built for publication: Pushable chromatic number of graphs with degree constraints