Circular chromatic number of signed graphs

DOI10.37236/9938zbMATH Open1466.05090arXiv2010.07525OpenAlexW3173806834MaRDI QIDQ2034071FDOQ2034071

Authors: Reza Naserasr, Zhouningxin Wang, Xuding Zhu 

Publication date: 21 June 2021

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

Abstract: A signed graph is a pair $(G,sigma)$, where $G$ is a graph and $sigma:E(G)o+,-$ is a signature which assigns to each edge of $G$ a sign. Various notions of coloring of signed graphs have been studied. In this paper, we extend circular coloring of graphs to signed graphs. Given a signed graph $(G,sigma)$ a circular $r$-coloring of $(G,sigma)$ is an assignment $psi$ of points of a circle of circumference $r$ to the vertices of $G$ such that for every edge $e=uv$ of $G$, if $sigma(e)=+$, then $psi(u)$ and $psi(v)$ have distance at least $1$, and if $sigma(e)=-$, then $psi(v)$ and the antipodal of $psi(u)$ have distance at least $1$. The circular chromatic number $ch{i}_c(G,sigma)$ of a signed graph $(G,sigma)$ is the infimum of those $r$ for which $(G,sigma)$ admits a circular $r$-coloring. For a graph $G$, we define the signed circular chromatic number of $G$ to be $$G$$. We study basic properties of circular coloring of signed graphs and develop tools for calculating $ch{i}_c(G,sigma)$. We explore the relation between the circular chromatic number and the signed circular chromatic number of graphs, and present bounds for the signed circular chromatic number of some families of graphs. In particular, we determine the supremum of the signed circular chromatic number of $k$-chromatic graphs of large girth, of simple bipartite planar graphs, $d$-degenerate graphs, simple outerplanar graphs and series-parallel graphs. We construct a signed planar simple graph whose circular chromatic number is $4+frac23$. This is based and improves on a signed graph built by Kardos and Narboni as a counterexample to a conjecture of M'{a}v{c}ajov'{a}, Raspaud, and v{S}koviera.

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

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

Recommendations

• Circular coloring of signed graphs
• Circular \({\boldsymbol{(4-\epsilon )}}\) -Coloring of Some Classes of Signed Graphs
• Signed bipartite circular cliques and a bipartite analogue of Grötzsch's theorem
• Signed planar graphs with given circular chromatic numbers
• On the signed chromatic number of some classes of graphs

zbMATH Keywords

circular coloring\(k\)-chromatic graphs

Mathematics Subject Classification ID

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

Cites Work

• Signed graphs
• Signed graph coloring
• Nowhere-zero 3-flows and modulo \(k\)-orientations
• On the odd-minor variant of Hadwiger's conjecture
• The chromatic number of a signed graph
• Recent developments in circular colouring of graphs
• Star chromatic number
• Star chromatic numbers and products of graphs
• Acyclic graph coloring and the complexity of the star chromatic number
• Circular chromatic number: A survey
• Coloring, sparseness and girth
• Homomorphisms of sparse signed graphs
• Circular flows of nearly Eulerian graphs and vertex-splitting
• (2 + ?)-Coloring of planar graphs with large odd-girth
• Hajos' graph-coloring conjecture: Variations and counterexamples
• High-girth graphs avoiding a minor are nearly bipartite
• The circular chromatic number of series-parallel graphs of large odd girth
• Title not available (Why is that?)
• The complexity of signed graph and edge-coloured graph homomorphisms
• Planar graphs with circular chromatic numbers between 3 and 4
• Homomorphisms of signed graphs
• The star-chromatic number of planar graphs
• Complexity of planar signed graph homomorphisms to cycles
• Homomorphisms of signed graphs: an update
• A note on not-4-list colorable planar graphs
• On the 4-color theorem for signed graphs
• A refinement of choosability of graphs
• A simple proof of Moser's theorem
• Density of 5/2-critical graphs
• Circular coloring of signed graphs
• Density of the circular chromatic numbers of series-parallel graphs

Cited In (17)

• The circular chromatic number of signed series-parallel graphs of given girth
• Signed planar graphs with given circular chromatic numbers
• Circular \({\boldsymbol{(4-\epsilon )}}\) -Coloring of Some Classes of Signed Graphs
• The chromatic number of a signed graph
• The chromatic spectrum of signed graphs
• On the signed chromatic number of some classes of graphs
• Density of 3-critical signed graphs
• Complex and homomorphic chromatic number of signed planar simple graphs
• Generalized signed graphs of large girth and large chromatic number
• Signed colouring and list colouring of k‐chromatic graphs
• Density of \(C_{-4}\)-critical signed graphs
• Signed bipartite circular cliques and a bipartite analogue of Grötzsch's theorem
• Mapping sparse signed graphs to (K2k,M) $({K}_{2k},M)$
• Symmetric set coloring of signed graphs
• Homomorphisms to small negative even cycles
• The circular chromatic numbers of signed series-parallel graphs
• Circular coloring of signed graphs

This page was built for publication: Circular chromatic number of signed graphs

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