On the signed chromatic number of some classes of graphs

DOI10.1016/j.disc.2021.112664zbMath1479.05093arXiv2009.12059OpenAlexW3204570097MaRDI QIDQ2666564

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

Publication date: 23 November 2021

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

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

zbMATH Keywords

planar graphbounded-degree graphtriangle-free planar graphsigned chromatic number\( K_n\)-minor-free graphhomomorphism of signed graphs

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Structural characterization of families of graphs (05C75) Coloring of graphs and hypergraphs (05C15) Graph minors (05C83) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Signed and weighted graphs (05C22)

Related Items

The chromatic number of signed graphs with bounded maximum average degree, Mapping sparse signed graphs to (K2k,M) $({K}_{2k},M)$, The chromatic number of 2-edge-colored and signed graphs of bounded maximum degree

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Characterisations and examples of graph classes with bounded expansion
• Edge-switching homomorphisms of edge-coloured graphs
• Signed graphs
• Homomorphisms of edge-colored graphs and Coxeter groups
• The extremal function for complete minors
• Homomorphism bounds and edge-colourings of \(K_{4}\)-minor-free graphs
• Homomorphisms of signed graphs: an update
• Induced subgraphs of hypercubes and a proof of the sensitivity conjecture
• The complexity of signed graph and edge-coloured graph homomorphisms
• Analogues of cliques for \((m,n)\)-colored mixed graphs
• Walk-powers and homomorphism bounds of planar signed graphs
• On Chromatic Number of Colored Mixed Graphs
• Acyclic and oriented chromatic numbers of graphs
• Homomorphisms of Signed Graphs
• Homomorphisms of 2‐Edge‐Colored Triangle‐Free Planar Graphs
• Homomorphisms of 2-edge-colored graphs