Circular coloring of signed graphs

DOI10.1002/JGT.22147MaRDI QIDQ4604021zbMATH OpenOpenAlexFDO

Authors Eckhard Steffen, Yingli Kang

Publication date 23 February 2018

Published in Journal of Graph Theory (Search for Journal in Brave)

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

zbMATH Keywords

circular chromatic numbercircular coloringssigned graphs

Mathematics Subject Classification ID

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

Abstract: Let $k,d$ ($2dleqk)$ be two positive integers. We generalize the well studied notions of $(k,d)$-colorings and of the circular chromatic number $ch{i}_c$ to signed graphs. This implies a new notion of colorings of signed graphs, and the corresponding chromatic number $chi$. Some basic facts on circular colorings of signed graphs and on the circular chromatic number are proved, and differences to the results on unsigned graphs are analyzed. In particular, we show that the difference between the circular chromatic number and the chromatic number of a signed graph is at most 1. Indeed, there are signed graphs where the difference is 1. On the other hand, for a signed graph on $n$ vertices, if the difference is smaller than 1, then there exists $epsilo{n}_n>0$, such that the difference is at most $1-epsilo{n}_n$. We also show that notion of $(k,d)$-colorings is equivalent to $r$-colorings (see (X. Zhu, Recent developments in circular coloring of graphs, in Topics in Discrete Mathematics Algorithms and Combinatorics Volume 26, Springer Berlin Heidelberg (2006) 497-550)).

Recommendations

• Circular chromatic number of signed graphs
• Circular \({\boldsymbol{(4-\epsilon )}}\) -Coloring of Some Classes of Signed Graphs
• The circular chromatic numbers of signed series-parallel graphs
• Signed bipartite circular cliques and a bipartite analogue of Grötzsch's theorem
• The chromatic spectrum of signed graphs

Cited in

(22)

• A sufficient condition for DP-4-colorability
• Circular chromatic number of signed graphs
• The circular chromatic numbers of signed series-parallel graphs
• Edge coloring of the signed generalized Petersen graph
• Generalized signed graphs of large girth and large chromatic number
• Signed planar graphs with given circular chromatic numbers
• 4-colouring of generalized signed planar graphs
• Homomorphisms of signed graphs: an update
• Concepts of signed graph coloring
• Colouring of \(S\)-labelled planar graphs
• Chromatic number and orientations of graphs and signed graphs
• Alon-Tarsi number and modulo Alon-Tarsi number of signed graphs
• The chromatic spectrum of signed graphs
• Planar graphs without intersecting 5-cycles are signed-4-choosable
• 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
• Signed bipartite circular cliques and a bipartite analogue of Grötzsch's theorem
• Symmetric set coloring of signed graphs
• Circular \({\boldsymbol{(4-\epsilon )}}\) -Coloring of Some Classes of Signed Graphs
• (I,F)-partition of planar graphs without cycles of length 4, 6, or 9
• Edge coloring of products of signed graphs

This page was built for publication: Circular coloring of signed graphs

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