The chromatic number of a signed graph

MaRDI QIDQ907266zbMATH OpenFDO

Authors E. Máčajová, Martin Škoviera, André Raspaud

Publication date 25 January 2016

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1412.6349, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i1p14

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

colouringsgraph theorysigned graph

Mathematics Subject Classification ID

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

Abstract: In 1982, Zaslavsky introduced the concept of a proper vertex colouring of a signed graph $G$ as a mapping $phicolonV(G)omathbbZ$ such that for any two adjacent vertices $u$ and $v$ the colour $phi(u)$ is different from the colour $sigma(uv)phi(v)$, where is $sigma(uv)$ is the sign of the edge $uv$. The substantial part of Zaslavsky's research concentrated on polynomial invariants related to signed graph colourings rather than on the behaviour of colourings of individual signed graphs. We continue the study of signed graph colourings by proposing the definition of a chromatic number for signed graphs which provides a natural extension of the chromatic number of an unsigned graph. We establish the basic properties of this invariant, provide bounds in terms of the chromatic number of the underlying unsigned graph, investigate the chromatic number of signed planar graphs, and prove an extension of the celebrated Brooks theorem to signed graphs.

Review text

Summary: In 1982, \textit{T. Zaslavsky} [Discrete Math. 39, 215--228 (1982; Zbl 0487.05027)] introduced the concept of a proper vertex colouring of a signed graph \(G\) as a mapping \(\phi: V(G)\to \mathbb{Z}\) such that for any two adjacent vertices \(u\) and \(v\) the colour \(\phi(u)\) is different from the colour \(\sigma(uv)\phi(v)\), where is \(\sigma(uv)\) is the sign of the edge \(uv\). The substantial part of Zaslavsky's research concentrated on polynomial invariants related to signed graph colourings rather than on the behaviour of colourings of individual signed graphs. We continue the study of signed graph colourings by proposing the definition of a chromatic number for signed graphs which provides a natural extension of the chromatic number of an unsigned graph. We establish the basic properties of this invariant, provide bounds in terms of the chromatic number of the underlying unsigned graph, investigate the chromatic number of signed planar graphs, and prove an extension of the celebrated Brooks' theorem to signed graphs.

Recommendations

• On the signed chromatic number of some classes of graphs
• The chromatic spectrum of signed graphs
• Chromatic number and orientations of graphs and signed graphs
• The chromatic number of joins of signed graphs
• Circular chromatic number of signed graphs
• Eigenvalues and chromatic number of a signed graph
• The sigma chromatic number of a graph
• On the achromatic number of signed graphs
• The odd-valued chromatic polynomial of a signed graph
• Chromatic number and signless Laplacian spectral radius of graphs

Cites work

• Brooks' Theorem and Beyond
• Chromatic invariants of signed graphs
• Graph Classes: A Survey
• How colorful the signed graph?
• scientific article; zbMATH DE number 1882351 (Why is no real title available?)
• scientific article; zbMATH DE number 3043302 (Why is no real title available?)
• On acyclic colorings of planar graphs
• On the notion of balance of a signed graph
• Signed graph coloring
• Signed graphs
• Three short proofs in graph theory

Cited in

(63)

• Every signed planar graph without cycles of length from 4 to 8 is 3-colorable
• Colouring of generalized signed triangle-free planar graphs
• A sufficient condition for DP-4-colorability
• Planar graphs without 4-cycles adjacent to triangles are DP-4-colorable
• Eigenvalues and chromatic number of a signed graph
• Circular chromatic number of signed graphs
• The chromatic number of joins of signed graphs
• The circular chromatic numbers of signed series-parallel graphs
• Density of \(C_{-4}\)-critical signed graphs
• Cover and variable degeneracy
• Complex and homomorphic chromatic number of signed planar simple graphs
• Edge coloring of the signed generalized Petersen graph
• Generalized signed graphs of large girth and large chromatic number
• A categorification for the signed chromatic polynomial
• Signed planar graphs with given circular chromatic numbers
• The odd-valued chromatic polynomial of a signed graph
• A generalization of Noel-Reed-Wu theorem to signed graphs
• Edge coloring of signed graphs
• 4-colouring of generalized signed planar graphs
• Tutte's dichromate for signed graphs
• On the 4-color theorem for signed graphs
• Homomorphisms of signed graphs: an update
• Concepts of signed graph coloring
• Colouring of \(S\)-labelled planar graphs
• Edge coloring signed graphs
• A refinement of choosability of graphs
• Chromatic number and orientations of graphs and signed graphs
• Alon-Tarsi number and modulo Alon-Tarsi number of signed graphs
• Hajós-like theorem for signed graphs
• The chromatic spectrum of signed graphs
• Generalising the achromatic number to Zaslavsky's colourings of signed graphs
• Vizing's adjacency lemma on edge chromatic critical signed graphs and its applications
• Coloring signed graphs using DFS
• Coloring permutation-gain graphs
• Coloring problem of signed interval graphs
• scientific article; zbMATH DE number 7614204 (Why is no real title available?)
• Planar graphs without intersecting 5-cycles are signed-4-choosable
• Not all planar graphs are in PURE-4-DIR
• Degree choosable signed graphs
• Nowhere-harmonic colorings of graphs
• Signed planar graphs with \(\Delta \geq 8\) are \(\Delta\)-edge-colorable
• Signed colouring and list colouring of k‐chromatic graphs
• On colorings and orientations of signed graphs
• The circular chromatic number of signed series-parallel graphs of given girth
• The sigma chromatic number of a graph
• Signed bipartite circular cliques and a bipartite analogue of Grötzsch's theorem
• Mapping sparse signed graphs to (K2k,M) $({K}_{2k},M)$
• Separating signatures in signed planar graphs
• Symmetric set coloring of signed graphs
• The list-coloring function of signed graphs
• Variable degeneracy on toroidal graphs
• Some new results on colour-induced signed graphs
• Homomorphisms to small negative even cycles
• Density of 3-critical signed graphs
• The four color theorem and its aftermath
• Chromatic polynomials of signed graphs and dominating-vertex deletion formulae
• (I,F)-partition of planar graphs without cycles of length 4, 6, or 9
• Edge coloring of products of signed graphs
• The homomorphism and coloring of the direct product of signed graphs
• Some orientation theorems for restricted DP-colorings of graphs
• On colorings and orientations of signed graphs. II
• Balanced chromatic number and Hadwiger-like conjectures
• How colorful the signed graph?

This page was built for publication: The chromatic number of a signed graph

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