Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userThe chromatic number of a signed graph
230
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
In 1982, Zaslavsky introduced the concept of a proper vertex colouring of a signed graph $G$ as a mapping $phicolon V(G)to mathbb{Z}$ such that for any two adjacent vertices $u$ and $v$ the colour $phi(u)$ is different from the colour $sigma(uv)phi(v)$, where is $sigma(uv)$ is the sign of the edge $uv$. The substantial part of Zaslavskys research concentrated on polynomial invariants related to signed graph colourings rather than on the behaviour of colourings of individual signed graphs. We continue the study of signed graph colourings by proposing the definition of a chromatic number for signed graphs which provides a natural extension of the chromatic number of an unsigned graph. We establish the basic properties of this invariant, provide bounds in terms of the chromatic number of the underlying unsigned graph, investigate the chromatic number of signed planar graphs, and prove an extension of the celebrated Brooks theorem to signed graphs.
rate research
Read More
A signed graph is a pair $(G, sigma)$, where $G$ is a graph 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)$ 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{a}v{c}ajov{a}, Raspaud, and v{S}koviera.
A signed graph $(G, sigma)$ is a graph with a sign attached to each of its edges, where $G$ is the underlying graph of $(G, sigma)$. Let $c(G)$, $alpha(G)$ and $r(G, sigma)$ be the cyclomatic number, the independence number and the rank of the adjacency matrix of $(G, sigma)$, respectively. In this paper, we study the relation among the independence number, the rank and the cyclomatic number of a signed graph $(G, sigma)$ with order $n$, and prove that $2n-2c(G) leq r(G, sigma)+2alpha(G) leq 2n$. Furthermore, the signed graphs that reaching the lower bound are investigated.
A signed graph is a pair $(G,Sigma)$, where $G=(V,E)$ is a graph (in which parallel edges are permitted, but loops are not) with $V={1,...,n}$ and $Sigmasubseteq E$. By $S(G,Sigma)$ we denote the set of all symmetric $Vtimes V$ matrices $A=[a_{i,j}]$ with $a_{i,j}<0$ if $i$ and $j$ are connected by only even edges, $a_{i,j}>0$ if $i$ and $j$ are connected by only odd edges, $a_{i,j}in mathbb{R}$ if $i$ and $j$ are connected by both even and odd edges, $a_{i,j}=0$ if $i ot=j$ and $i$ and $j$ are non-adjacent, and $a_{i,i} in mathbb{R}$ for all vertices $i$. The stable inertia set of a signed graph $(G,Sigma)$ is the set of all pairs $(p,q)$ for which there exists a matrix $Ain S(G,Sigma)$ with $p$ positive and $q$ negative eigenvalues which has the Strong Arnold Property. In this paper, we study the stable inertia set of (signed) graphs.
We determine the asymptotic behaviour of the chromatic number of exchangeable random graphs defined by step-regulated graphons. Furthermore, we show that the upper bound holds for a general graphon. We also extend these results to sparse random graphs obtained by percolations on graphons.
A signed graph $Gamma(G)$ is a graph with a sign attached to each of its edges, where $G$ is the underlying graph of $Gamma(G)$. The energy of a signed graph $Gamma(G)$ is the sum of the absolute values of the eigenvalues of the adjacency matrix $A(Gamma(G))$ of $Gamma(G)$. The random signed graph model $mathcal{G}_n(p, q)$ is defined as follows: Let $p, q ge 0$ be fixed, $0 le p+q le 1$. Given a set of $n$ vertices, between each pair of distinct vertices there is either a positive edge with probability $p$ or a negative edge with probability $q$, or else there is no edge with probability $1-(p+ q)$. The edges between different pairs of vertices are chosen independently. In this paper, we obtain an exact estimate of energy for almost all signed graphs. Furthermore, we establish lower and upper bounds to the energy of random multipartite signed graphs.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
