On the signed chromatic number of some classes of graphs

DOI10.1016/J.DISC.2021.112664MaRDI QIDQ2666564zbMATH OpenOpenAlexFDO

Authors Julien Bensmail, Sandip Das, Soumen Nandi, Théo Pierron, Sagnik Sen, Éric 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

\( K_n\)-minor-free graphbounded-degree graphhomomorphism of signed graphsplanar graphsigned chromatic numbertriangle-free planar graph

Mathematics Subject Classification ID

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

Abstract: A signed graph $(G,sigma)$ is a graph $G$ along with a function $sigma:E(G)o+,-$. A closed walk of a signed graph is positive (resp., negative) if it has an even (resp., odd) number of negative edges, counting repetitions. A homomorphism of a (simple) signed graph to another signed graph is a vertex-mapping that preserves adjacencies and signs of closed walks. The signed chromatic number of a signed graph $(G,sigma)$ is the minimum number of vertices $|V(H)|$ of a signed graph $(H,pi)$ to which $(G,sigma)$ admits a homomorphism.Homomorphisms of signed graphs have been attracting growing attention in the last decades, especially due to their strong connections to the theories of graph coloring and graph minors. These homomorphisms have been particularly studied through the scope of the signed chromatic number. In this work, we provide new results and bounds on the signed chromatic number of several families of signed graphs (planar graphs, triangle-free planar graphs, $K_n$-minor-free graphs, and bounded-degree graphs).

Recommendations

• Homomorphisms of signed graphs
• Homomorphisms of signed graphs: an update
• Circular chromatic number of signed graphs
• On the chromatic numbers of signed triangular and hexagonal grids
• The chromatic spectrum of signed graphs

Cites work

• Acyclic and oriented chromatic numbers of graphs
• Analogues of cliques for \((m,n)\)-colored mixed graphs
• Characterisations and examples of graph classes with bounded expansion
• Classification of edge-critical underlying absolute planar cliques for signed graphs
• Edge-switching homomorphisms of edge-coloured graphs
• Homomorphism bounds and edge-colourings of \(K_{4}\)-minor-free graphs
• Homomorphisms of 2-edge-colored graphs
• Homomorphisms of 2-edge-colored triangle-free planar graphs
• Homomorphisms of edge-colored graphs and Coxeter groups
• Homomorphisms of planar signed graphs to signed projective cubes
• Homomorphisms of signed graphs
• Homomorphisms of signed graphs: an update
• scientific article; zbMATH DE number 7559433 (Why is no real title available?)
• Induced subgraphs of hypercubes and a proof of the sensitivity conjecture
• On chromatic number of colored mixed graphs
• Signed graphs
• The complexity of signed graph and edge-coloured graph homomorphisms
• The extremal function for complete minors
• Walk-powers and homomorphism bounds of planar signed graphs

Cited in

(19)

• Circular chromatic number of signed graphs
• The chromatic number of joins of signed graphs
• The chromatic number of signed graphs with bounded maximum average degree
• Alternating signed bipartite graphs and difference-1 colourings
• Homomorphisms of signed graphs: an update
• On the chromatic numbers of signed triangular and hexagonal grids
• Generalising the achromatic number to Zaslavsky's colourings of signed graphs
• Classification of edge-critical underlying absolute planar cliques for signed graphs
• Bounding signed series-parallel graphs and cores of signed K₄-subdivisions
• The homomorphism order of signed graphs
• The chromatic polynomials of signed Petersen graphs
• Homomorphisms of signed graphs
• On colorings and orientations of signed graphs
• Mapping sparse signed graphs to (K2k,M) $({K}_{2k},M)$
• Some new results on colour-induced signed graphs
• The chromatic number of 2-edge-colored and signed graphs of bounded maximum degree
• Extended double covers and homomorphism bounds of signed graphs
• On coloring parameters of triangle-free planar (n, m)-graphs
• The chromatic number of a signed graph

This page was built for publication: On the signed chromatic number of some classes of graphs

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