Circular chromatic number of signed graphs

DOI10.37236/9938MaRDI QIDQ2034071zbMATH OpenOpenAlexFDO

Authors Reza Naserasr, Zhouningxin Wang, Xuding Zhu

Publication date 21 June 2021

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

Copyright license Creative Commons Attribution 4.0 International

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

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

circular coloring\(k\)-chromatic graphs

Mathematics Subject Classification ID

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

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.

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

Cites work

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

Cited in

(17)

• Signed planar graphs with given circular chromatic numbers
• The circular chromatic number of signed series-parallel graphs of given girth
• 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)