The signed domatic number of some regular graphs

Let G be a finite and simple graph with vertex set V(G), and let f:V(G)→{−1,1} be a two-valued function. If ∑_x∈N[v]f(x)≥1 for each v∈V(G), where N[v] is the closed neighborhood of v, then f is a signed dominating function on G. A set {f₁,f₂,…,f_d} of signed dominating functions on G with the property that for each x∈V(G), is called a signed dominating family (of functions) on G. The maximum number of functions in a signed dominating family on G is the signed domatic number on G. In this paper, we investigate the signed domatic number of some circulant graphs and of the torus C_p×C_q.     

THE TOTAL CHROMATIC NUMBER OF PSEUDO-OUTERPLANAR GRAPHS

A Planar graph g is called a ipseudo outerplanar graph if there is a subset v.∈V(G),[V.]=i,such that G-V. is an outerplanar graph in particular when G-V.is a forest ,g is called a i-pseudo-tree .in this paper.the following results are proved;(1)the conjecture on the total coloring is true for all 1-pseudo-outerplanar graphs;(2)X1(G) 1 fo any 1-pseudo outerplanar graph g with △(G)≥3,where x4(G)is the total chromatic number of a graph g.     

Star chromatic numbers of some planar graphs

The concept of the star chromatic number of a graph was introduced by Vince (A. Vince, Star chromatic number, J. Graph Theory 12 (1988), 551–559), which is a natural generalization of the chromatic number of a graph. This paper calculates the star chromatic numbers of three infinite families of planar graphs. More precisely, the first family of planar graphs has star chromatic numbers consisting of two alternating infinite decreasing sequences between 3 and 4; the second family of planar graphs has star chromatic numbers forming an infinite decreasing sequence between 3 and 4; and the third family of planar graphs has star chromatic number 7/2. © 1998 John Wiley & Sons, Inc. J Graph Theory 27: 33–42, 1998     

On signed cycle domination in graphs

Let G=(V,E) be a graph, a function f:E→{−1,1} is said to be an signed cycle dominating function (SCDF) of G if ∑_e∈E(C)f(e)≥1 holds for any induced cycle C of G. The signed cycle domination number of G is defined as is an SCDF of G}. In this paper, we obtain bounds on , characterize all connected graphs G with , and determine the exact value of for some special classes of graphs G. In addition, we pose some open problems and conjectures.     

Colouring of generalized signed triangle-free planar graphs

We view an undirected graph $G$ as a symmetric digraph, where each edge $xy$ is replaced by two opposite arcs $e=(x,y)$ and $e^{?1}=(y,x)$. Assume $S$ is an inverse closed subset of permutations of positive integers. We say $G$ is $S$-$k$-colourable if for any mapping $\sigma :E\left(G\right)\to S$ with $\sigma (x,y)={\left(\sigma (y,x)\right)}^{?1}$, there is a mapping $f:V\left(G\right)\to \left[k\right]=\{1,2,\dots ,k\}$ such that ${\sigma }_e\left(f\left(x\right)\right)\ne f\left(y\right)$ for each arc $e=(x,y)$. The concept of $S$-$k$-colourable is a common generalization of several other colouring concepts. This paper is focused on finding the sets $S$ such that every triangle-free planar graph is $S$-3-colourable. Such a set $S$ is called TFP-good. Grötzsch’s theorem is equivalent to say that $S=\left\{id\right\}$ is TFP-good. We prove that for any inverse closed subset $S$ of $S_3$ which is not isomorphic to $\{id,\left(12\right)\}$, $S$ is TFP-good if and only if either $S=\left\{id\right\}$ or there exists $a\in \left[3\right]$ such that for each $\pi \in S$, $\pi \left(a\right)\ne a$. It remains an open question to determine whether or not $S=\{id,\left(12\right)\}$ is TFP-good.     

Circular game chromatic number of graphs

In a circular r-colouring game on G, Alice and Bob take turns colouring the vertices of G with colours from the circle S(r) of perimeter r. Colours assigned to adjacent vertices need to have distance at least 1 in S(r). Alice wins the game if all vertices are coloured, and Bob wins the game if some uncoloured vertices have no legal colour. The circular game chromatic number χ_cg(G) of G is the infimum of those real numbers r for which Alice has a winning strategy in the circular r-colouring game on G. This paper proves that for any graph G, , where is the game colouring number of G. This upper bound is shown to be sharp for forests. It is also shown that for any graph G, χ_cg(G)≤2χ_a(G)(χ_a(G)+1), where χ_a(G) is the acyclic chromatic number of G. We also determine the exact value of the circular game chromatic number of some special graphs, including complete graphs, paths, and cycles.     

On total chromatic number of planar graphs without 4-cycles

Let G be a simple graph with maximum degree A(G) and total chromatic number Xve(G). Vizing conjectured thatΔ(G) 1≤Xve(G)≤Δ(G) 2 (Total Chromatic Conjecture). Even for planar graphs, this conjecture has not been settled yet. The unsettled difficult case for planar graphs isΔ(G) = 6. This paper shows that if G is a simple planar graph with maximum degree 6 and without 4-cycles, then Xve(G)≤8. Together with the previous results on this topic, this shows that every simple planar graph without 4-cycles satisfies the Total Chromatic Conjecture.     

Circular coloring of signed graphs

Let ( be two positive integers. We generalize the well‐studied notions of ‐colorings and of the circular chromatic number to signed graphs. This implies a new notion of colorings of signed graphs, and the corresponding chromatic number χ. 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 , such that the difference is at most . We also show that the notion of ‐colorings is equivalent to r‐colorings (see [12] (X. Zhu, Recent developments in circular coloring of graphs, in Topics in Discrete Mathematics Algorithms and Combinatorics Volume 26 , Springer Berlin Heidelberg, 2006, pp. 497–550)).     

On the chromatic number of random graphs

We consider random graphs G_n,p with fixed edge-probability p. We refine an argument of Bollobás to show that almost all such graphs have chromatic number equal to n/{2 log_b n ? 2 log_b log_b n + O(1)} where b = 1/(1 ? p).     

On the complete chromatic number of Halin graphs

ThisresearchissupportedbytheNationalNaturalScienceFoundationofChina.Write.1.IntroductionDefinition1.FOrany3-connectedplanargraphG(V,E,F)withA(G)23,iftheboundaryedgesoffacefowhichisadjacenttotheothersareremoved,itbecomesatree,andthedegreeofeachvertexofV(fo)is3,andthenGiscalledaHalingraph;foiscalledtheouterfaceofG,andtheotherscalledtheinteriorfaces,thevenicesonthefacefoarecalledtheoutervenices,theoillersarecalledtheinterior...ti..,tll.ForanyplanargraphG(V,E,F),f,f'eF,fisadjacenttof'ifan…     

The chromatic number of dense random graphs

The chromatic number of a graph G is defined as the minimum number of colors required for a vertex coloring where no two adjacent vertices are colored the same. The chromatic number of the dense random graph where is constant has been intensively studied since the 1970s, and a landmark result by Bollobás in 1987 first established the asymptotic value of . Despite several improvements of this result, the exact value of remains open. In this paper, new upper and lower bounds for are established. These bounds are the first ones that match each other up to a term of size o(1) in the denominator: they narrow down the coloring rate of to an explicit interval of length o(1), answering a question of Kang and McDiarmid.     

Flow number and circular flow number of signed cubic graphs

Let $\mathrm{\Phi }(G,\sigma )$ and ${\mathrm{\Phi }}_c(G,\sigma )$ denote the flow number and the circular flow number of a flow-admissible signed graph $(G,\sigma )$, respectively. It is known that $\mathrm{\Phi }(G)=?{\mathrm{\Phi }}_c(G)?$ for every unsigned graph G. Based on this fact, in 2011 Raspaud and Zhu conjectured that $\mathrm{\Phi }(G,\sigma )?{\mathrm{\Phi }}_c(G,\sigma )<1$ holds also for every flow-admissible signed graph $(G,\sigma )$. This conjecture was disproved by Schubert and Steffen using graphs with bridges and vertices of large degree. In this paper we focus on cubic graphs, since they play a crucial role in many open problems in graph theory. For cubic graphs we show that $\mathrm{\Phi }(G,\sigma )=3$ if and only if ${\mathrm{\Phi }}_c(G,\sigma )=3$ and if $\mathrm{\Phi }(G,\sigma )\in \{4,5\}$, then $4\le {\mathrm{\Phi }}_c(G,\sigma )\le \mathrm{\Phi }(G,\sigma )$. We also prove that all pairs of flow number and circular flow number that fulfil these conditions can be achieved in the family of bridgeless cubic graphs and thereby disprove the conjecture of Raspaud and Zhu even for bridgeless signed cubic graphs. Finally, we prove that all currently known flow-admissible graphs without nowhere-zero 5-flow have flow number and circular flow number 6 and propose several conjectures in this area.     

On the circular chromatic number of circular partitionable graphs

This article studies the circular chromatic number of a class of circular partitionable graphs. We prove that an infinite family of circular partitionable graphs G has . A consequence of this result is that we obtain an infinite family of graphs G with the rare property that the deletion of each vertex decreases its circular chromatic number by exactly 1. © 2006 Wiley Periodicals, Inc. J Graph Theory     

Total chromatic number of planar graphs with maximum degree ten

In this article we prove that the total chromatic number of a planar graph with maximum degree 10 is 11. © 2006 Wiley Periodicals, Inc. J Graph Theory 54: 91–102, 2007     

Distinguishing chromatic number of random Cayley graphs

The distinguishing chromatic number of a graph $G$, denoted ${\chi }_D\left(G\right)$, is defined as the minimum number of colors needed to properly color $G$ such that no non-trivial automorphism of $G$ fixes each color class of $G$. In this paper, we consider random Cayley graphs $\Gamma$ defined over certain abelian groups $A$ with $\left|A\right|=n$, and show that with probability at least $1?n^{?\Omega (logn)}$, ${\chi }_D\left(\Gamma \right)\le \chi \left(\Gamma \right)+1$.