Degree choosable signed graphs

DOI10.1016/J.DISC.2017.01.007zbMATH Open1357.05055arXiv1507.04569OpenAlexW2964125446MaRDI QIDQ512558FDOQ512558

Authors: Thomas Schweser, Michael Stiebitz 

Publication date: 27 February 2017

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

Abstract: A signed graph is a graph in which each edge is labeled with $+1$ or $-1$. A (proper) vertex coloring of a signed graph is a mapping $f$ that assigns to each vertex $vinV(G)$ a color $f(v)inmz$ such that every edge $vw$ of $G$ satisfies $f(v)ot=sg(vw)f(w)$, where $sg(vw)$ is the sign of the edge $vw$. For an integer $hgeq0$, let $G{a}_{2h}=pm1,pm2,ldots,pmh$ and $G{a}_{2h+1}=G{a}_{2h}cup0$. Following cite{MaRS2015}, the signed chromatic number $scn(G)$ of $G$ is the least integer $k$ such that $G$ admits a vertex coloring $f$ with $mim(f)subseteqG{a}_k$. As proved in cite{MaRS2015}, every signed graph $G$ satisfies $scn(G)leqDe(G)+1$ and there are three types of signed connected simple graphs for which equality holds. We will extend this Brooks' type result by considering graphs having multiple edges. We will also proof a list version of this result by characterizing degree choosable signed graphs. Furthermore, we will establish some basic facts about color critical signed graphs.

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

Recommendations

• The chromatic number of a signed graph
• The chromatic spectrum of signed graphs
• Signed colouring and list colouring of k‐chromatic graphs
• Edge coloring of signed graphs
• Edge coloring signed graphs

zbMATH Keywords

graph coloringlist coloringsigned graphs

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Signed and weighted graphs (05C22) Graph labelling (graceful graphs, bandwidth, etc.) (05C78)

Cites Work

• Signed graphs
• Signed graph coloring
• On the notion of balance of a signed graph
• Title not available (Why is that?)
• Title not available (Why is that?)
• Every planar graph is 5-choosable
• The chromatic number of a signed graph
• Title not available (Why is that?)
• Dirac's map-color theorem for choosability
• Chromatic invariants of signed graphs
• The colour theorems of Brooks and Gallai extended
• Enumeration of weak isomorphism classes of signed graphs
• The last excluded case of Dirac's map‐color theorem for choosability
• How colorful the signed graph?
• Choosability in signed planar graphs

Cited In (13)

• Hajós-like theorem for signed graphs
• Variable degeneracy on toroidal graphs
• Coloring signed graphs using DFS
• Concepts of signed graph coloring
• A generalization of Noel-Reed-Wu theorem to signed graphs
• Alon-Tarsi number and modulo Alon-Tarsi number of signed graphs
• Title not available (Why is that?)
• The chromatic spectrum of signed graphs
• Signed colouring and list colouring of k‐chromatic graphs
• Signed graph factors and degree sequences
• Symmetric set coloring of signed graphs
• Cover and variable degeneracy
• How colorful the signed graph?

This page was built for publication: Degree choosable signed graphs

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