The chromatic spectrum of signed graphs

DOI10.1016/J.DISC.2016.05.013MaRDI QIDQ2629274zbMATH OpenOpenAlexFDO

Authors Yingli Kang, Eckhard Steffen

Publication date 5 July 2016

Published in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

chromatic numberchromatic spectrumsigned graphsvertex coloring

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Signed and weighted graphs (05C22)

Abstract: The chromatic number $chi((G,sigma))$ of a signed graph $(G,sigma)$ is the smallest number $k$ for which there is a function $c:V(G)ightarrowmathbb{Z}_k$ such that $c(v)ot=sigma(e)c(w)$ for every edge $e=vw$. Let $Sigma(G)$ be the set of all signatures of $G$. We study the chromatic spectrum $Sigm{a}_{chi}(G)=chi((G,sigma))colonsigmainSigma(G)$ of $(G,sigma)$. Let $M_{chi}(G)=maxchi((G,sigma))colonsigmainSigma(G)$, and $m_{chi}(G)=minchi((G,sigma))colonsigmainSigma(G)$. We show that $Sigm{a}_{chi}(G)=k:m_{chi}(G)leqkleq{M}_{chi}(G)$. We also prove some basic facts for critical graphs. Analogous results are obtained for a notion of vertex-coloring of signed graphs which was introduced by M'{a}v{c}ajov'{a}, Raspaud, and v{S}koviera.

Recommendations

• Eigenvalues and chromatic number of a signed graph
• How colorful the signed graph?
• The chromatic number of a signed graph
• Degree choosable signed graphs
• Circular chromatic number of signed graphs

Cites work

• Chromatic invariants of signed graphs
• Circular coloring of signed graphs
• Circular flow on signed graphs
• Degree choosable signed graphs
• How colorful the signed graph?
• Signed graph coloring
• The chromatic number of a signed graph

Cited in

(34)

• Signed analogs of bipartite graphs
• A sufficient condition for DP-4-colorability
• Eigenvalues and chromatic number of a signed graph
• The chromatic number of joins of signed graphs
• The chromatic number of signed graphs with bounded maximum average degree
• Generalized signed graphs of large girth and large chromatic number
• The odd-valued chromatic polynomial of a signed graph
• 4-colouring of generalized signed planar graphs
• Alternating signed bipartite graphs and difference-1 colourings
• Concepts of signed graph coloring
• Colouring of \(S\)-labelled planar graphs
• A refinement of choosability of graphs
• Chromatic number and orientations of graphs and signed graphs
• Hajós-like theorem for signed graphs
• On the signed chromatic number of some classes of graphs
• Generalising the achromatic number to Zaslavsky's colourings of signed graphs
• On monochromatic spectra in graphs
• A note on the vertex arboricity of signed graphs
• Circular coloring of signed graphs
• Coloring permutation-gain graphs
• The chromatic polynomials of signed Petersen graphs
• Chromatic polynomials of signed book graphs
• Planar graphs without intersecting 5-cycles are signed-4-choosable
• Chromatic number and signless Laplacian spectral radius of graphs
• Degree choosable signed graphs
• Signed colouring and list colouring of k‐chromatic graphs
• On colorings and orientations of signed graphs
• Edge coloring of graphs of signed class 1 and 2
• Symmetric set coloring of signed graphs
• Some new results on colour-induced signed graphs
• Edge coloring of products of signed graphs
• The homomorphism and coloring of the direct product of signed graphs
• How colorful the signed graph?
• The chromatic number of a signed graph

This page was built for publication: The chromatic spectrum of signed graphs

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