Circular chromatic number of signed graphs
The electronic journal of combinatorics, Tome 28 (2021) no. 2
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

A signed graph is a pair $(G, \sigma)$, where $G$ is a graph (loops and multi edges allowed) and $\sigma: E(G) \to \{+, -\}$ 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)$ with no positive loop, 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 $\chi_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 $\max\{\chi_c(G, \sigma): \sigma \text{ is a signature of $G$}\}$. We study basic properties of circular coloring of signed graphs and develop tools for calculating $\chi_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+\frac{2}{3}$. This is based and improves on a signed graph built by Kardos and Narboni as a counterexample to a conjecture of Máčajová, Raspaud, and Škoviera.
DOI : 10.37236/9938
Classification : 05C22, 05C15
Mots-clés : circular coloring, \(k\)-chromatic graphs

Reza Naserasr  1   ; Zhouningxin Wang  2   ; Xuding Zhu  3

1 université PARIS DIDEROT
2 Université de Paris
3 Zhejiang Normal University, Jinhua
@article{10_37236_9938,
     author = {Reza Naserasr and Zhouningxin Wang and Xuding Zhu},
     title = {Circular chromatic number of signed graphs},
     journal = {The electronic journal of combinatorics},
     year = {2021},
     volume = {28},
     number = {2},
     doi = {10.37236/9938},
     zbl = {1466.05090},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/9938/}
}
TY  - JOUR
AU  - Reza Naserasr
AU  - Zhouningxin Wang
AU  - Xuding Zhu
TI  - Circular chromatic number of signed graphs
JO  - The electronic journal of combinatorics
PY  - 2021
VL  - 28
IS  - 2
UR  - http://geodesic.mathdoc.fr/articles/10.37236/9938/
DO  - 10.37236/9938
ID  - 10_37236_9938
ER  - 
%0 Journal Article
%A Reza Naserasr
%A Zhouningxin Wang
%A Xuding Zhu
%T Circular chromatic number of signed graphs
%J The electronic journal of combinatorics
%D 2021
%V 28
%N 2
%U http://geodesic.mathdoc.fr/articles/10.37236/9938/
%R 10.37236/9938
%F 10_37236_9938
Reza Naserasr; Zhouningxin Wang; Xuding Zhu. Circular chromatic number of signed graphs. The electronic journal of combinatorics, Tome 28 (2021) no. 2. doi: 10.37236/9938

Cité par Sources :