Game chromatic number of outerplanar graphs

This note proves that the game chromatic number of an outerplanar graph is at most 7. This improves the previous known upper bound of the game chromatic number of outerplanar graphs. © 1999 John Wiley & Sons, Inc. J Graph Theory 30: 67–70, 1999     

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.     

The relaxed game chromatic number of outerplanar graphs

The (r,d)‐relaxed coloring game is played by two players, Alice and Bob, on a graph G with a set of r colors. The players take turns coloring uncolored vertices with legal colors. A color α is legal for an uncolored vertex u if u is adjacent to at most d vertices that have already been colored with α, and every neighbor of u that has already been colored with α is adjacent to at most d – 1 vertices that have already been colored with α. Alice wins the game if eventually all the vertices are legally colored; otherwise, Bob wins the game when there comes a time when there is no legal move left. We show that if G is outerplanar then Alice can win the (2,8)‐relaxed coloring game on G. It is known that there exists an outerplanar graph G such that Bob can win the (2,4)‐relaxed coloring game on G. © 2004 Wiley Periodicals, Inc. J Graph Theory 46:69–78, 2004     

The incidence game chromatic number of paths and subgraphs of wheels

The incidence game chromatic number was introduced to unify the ideas of the incidence coloring number and the game chromatic number. We determine the exact incidence game chromatic number of large paths and give a correct proof of a result stated by Andres [S.D. Andres, The incidence game chromatic number, Discrete Appl. Math. 157 (2009) 1980-1987] concerning the exact incidence game chromatic number of large wheels.     

The game chromatic index of wheels

We prove that the game chromatic index of n-wheels is n for n≥6.     

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.     

Edge‐face chromatic number and edge chromatic number of simple plane graphs

Given a simple plane graph G, an edge‐face k‐coloring of G is a function ? : E(G) ∪ F(G) → {1,…,k} such that, for any two adjacent or incident elements a, b ∈ E(G) ∪ F(G), ?(a) ≠ ?(b). Let χ_e(G), χ_ef(G), and Δ(G) denote the edge chromatic number, the edge‐face chromatic number, and the maximum degree of G, respectively. In this paper, we prove that χ_ef(G) = χ_e(G) = Δ(G) for any 2‐connected simple plane graph G with Δ (G) ≥ 24. © 2005 Wiley Periodicals, Inc. J Graph Theory     

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.     

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$.     

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…     

Fractional chromatic number and circular chromatic number for distance graphs with large clique size

An Erratum has been published for this article in Journal of Graph Theory 48: 329–330, 2005 . Let M be a set of positive integers. The distance graph generated by M, denoted by G(Z, M), has the set Z of all integers as the vertex set, and edges ij whenever |i?j| ∈ M. We investigate the fractional chromatic number and the circular chromatic number for distance graphs, and discuss their close connections with some number theory problems. In particular, we determine the fractional chromatic number and the circular chromatic number for all distance graphs G(Z, M) with clique size at least |M|, except for one case of such graphs. For the exceptional case, a lower bound for the fractional chromatic number and an upper bound for the circular chromatic number are presented; these bounds are sharp enough to determine the chromatic number for such graphs. Our results confirm a conjecture of Rabinowitz and Proulx 22 on the density of integral sets with missing differences, and generalize some known results on the circular chromatic number of distance graphs and the parameter involved in the Wills' conjecture 26 (also known as the “lonely runner conjecture” 1 ). © 2004 Wiley Periodicals, Inc. J Graph Theory 47: 129–146, 2004     

CHROMATIC NUMBER OF SQUARE OF MAXIMAL OUTERPLANAR GRAPHS

Let x（G^2） denote the chromatic number of the square of a maximal outerplanar graph G and Q denote a maximal outerplanar graph obtained by adding three chords y1 y3, y3y5, y5y1 to a 6-cycle y1y2…y6y1. In this paper, it is proved that △ ＋ 1 ≤ x（G^2） ≤△ ＋ 2, and x（G^2） = A ＋ 2 if and only if G is Q, where A represents the maximum degree of G.     

Game chromatic index of k‐degenerate graphs

We consider the following edge coloring game on a graph G. Given t distinct colors, two players Alice and Bob, with Alice moving first, alternately select an uncolored edge e of G and assign it a color different from the colors of edges adjacent to e. Bob wins if, at any stage of the game, there is an uncolored edge adjacent to colored edges in all t colors; otherwise Alice wins. Note that when Alice wins, all edges of G are properly colored. The game chromatic index of a graph G is the minimum number of colors for which Alice has a winning strategy. In this paper, we study the edge coloring game on k‐degenerate graphs. We prove that the game chromatic index of a k‐degenerate graph is at most Δ + 3k − 1, where Δ is the maximum vertex degree of the graph. We also show that the game chromatic index of a forest of maximum degree 3 is at most 4 when the forest contains an odd number of edges. © 2001 John Wiley & Sons, Inc. J Graph Theory 36: 144–155, 2001     

Orientations of graphs with uncountable chromatic number

Motivated by an old conjecture of P. Erdős and V. Neumann‐Lara, our aim is to investigate digraphs with uncountable dichromatic number and orientations of undirected graphs with uncountable chromatic number. A graph has uncountable chromatic number if its vertices cannot be covered by countably many independent sets, and a digraph has uncountable dichromatic number if its vertices cannot be covered by countably many acyclic sets. We prove that, consistently, there are digraphs with uncountable dichromatic number and arbitrarily large digirth; this is in surprising contrast with the undirected case: any graph with uncountable chromatic number contains a 4‐cycle. Next, we prove that several well‐known graphs (uncountable complete graphs, certain comparability graphs, and shift graphs) admit orientations with uncountable dichromatic number in ZFC. However, we show that the statement “every graph G of size and chromatic number ω₁ has an orientation D with uncountable dichromatic number” is independent of ZFC. We end the article with several open problems.     

The total chromatic number of Pseudo-Halin graphs with lower degree

The total chromatic number χ_T(G) of a graph G is the least number of colors needed to color the vertices and the edges of G such that no adjacent or incident elements receive the same color. The Total Coloring Conjecture(TCC) states that for every simple graph G, χ_T(G)≤Δ(G)+2. In this paper, we show that χ_T(G)=Δ(G)+1 for all pseudo-Halin graphs with Δ(G)=4 and 5.     

The total chromatic number of regular graphs of high degree

The total chromatic number χT (G) of a graph G is the minimum number of colors needed to color the edges and the vertices of G so that incident or adjacent elements have distinct colors. We show that if G is a regular graph and d(G) 32 |V (G)| + 263 , where d(G) denotes the degree of a vertex in G, then χT (G) d(G) + 2.