Equitable Coloring of Complete r-partite Graphs

A graph is equitably k-colorable if its vertices can be partitioned into k independent sets of as near equal sizes as possible. In this paper, we determine a sufficient and necessary condition for which a complete r-partite graph is equitably k-colorable. From this result, we can provide another way to prove some previous results.     

1-planar Graphs without 4-cycles or 5-cycles are 5-colorable

A graph is 1-planar if it can be drawn on the Euclidean plane so that each edge is crossed by at most one other edge. A proper vertex k-coloring of a graph G is defined as a vertex coloring from a set of k colors such that no two adjacent vertices have the same color. A graph that can be assigned a proper k-coloring is k-colorable. A cycle is a path of edges and vertices wherein a vertex is reachable from itself. A cycle contains k vertices and k edges is a k-cycle. In this paper, it is proved t...     

Equitable Vertex Arboricity Conjecture Holds for Graphs with Low Degeneracy

The equitable tree-coloring can formulate a structure decomposition problem on the communication network with some security considerations. Namely, an equitable tree-k-coloring of a graph is a vertex coloring using k distinct colors such that every color class induces a forest and the sizes of any two color classes differ by at most one. In this paper, we show some theoretical results on the equitable tree-coloring of graphs by proving that every d-degenerate graph with maximum degree at most Δ is equitably tree-k-colorable for every integer k ≥(Δ + 1)/2 provided that Δ≥ 9.818 d,confirming the equitable vertex arboricity conjecture for graphs with low degeneracy.     

k-fold coloring of planar graphs

A k-fold n-coloring of G is a mapping φ: V (G) → Zk(n) where Zk(n) is the collection of all ksubsets of {1,2,...,n} such that φ(u) ∩φ(v) = φ if uv ∈ E(G).If G has a k-fold n-coloring,i.e.,G is k-fold n-colorable.Let the smallest integer n such that G is k-fold n-colorable be the k-th chromatic number,denoted by χk(G).In this paper,we show that any outerplanar graph is k-fold 2k-colorable or k-fold χk(C*)-colorable,where C* is a shortest odd cycle of G.Moreover,we investigate that every planar graph with odd girth at least 10k-9(k 3) can be k-fold (2k + 1)-colorable.     

The genus of a type of graph

Based on the joint tree model introduced by Liu, the genera of further types of graphs not necessary to have certain symmetry can be obtained. In this paper, we obtain the genus of a new type of graph with weak symmetry. As a corollary, the genus of complete tripartite graph K n,n,l (l≥n≥2) is also derived. The method used here is more direct than those methods, such as current graph, used to calculate the genus of a graph and can be realized in polynomial time.     

Problems on Two-dimensional Bandwidth under Distance of L_∞-norm

The two-dimensional bandwidth problem is to determine an embedding of graph G in a grid graph in the plane such that the longest edges are as short as possible. In this paper we study the problem under the distance of L∞-norm.     

L∞模下的二维带宽问题

The two-dimensional bandwidth problem is to determine an embedding of graph G in a grid graph in the plane such that the longest edges are as short as possible. In this paper we study the problem under the distance of L∞-norm.     

On second order degree of graphs

Given a vertex v of a graph G the second order degree of v denoted as d 2(v) is defined as the number of vertices at distance 2 from v.In this paper we address the following question:What are the sufficient conditions for a graph to have a vertex v such that d2(v) ≥ d(v),where d(v) denotes the degree of v? Among other results,every graph of minimum degree exactly 2,except four graphs,is shown to have a vertex of second order degree as large as its own degree.Moreover,every K-4-free graph or every maximal planar graph is shown to have a vertex v such that d2(v) ≥ d(v).Other sufficient conditions on graphs for guaranteeing this property are also proved.     

几乎交错环链补中的不可压缩曲面

In this paper,we discuss mainly the properties of incompressible pairwies incom- prcssiblc surfaccs in almost altcrnating link complcmcnts. Lct L bca almost link and lct F be an incompressible palrwise incompressible surface in S~3-L.First,we give the properties that the surface F intersects with 2-spheres in S~3-L.The intersection consisting of a collection of circles and saddle-shaped discs is called a topological graph.One can compute the Euler Characteristic number of the surface by calculating the characteristic number of the graph.Next,we prove that if the graph is special simple,then the genus of the surface is zero.     

Conflict-free Connection Number and Independence Number of a Graph

An edge-colored graph G is conflict-free connected if any two of its vertices are connected by a path,which contains a color used on exactly one of its edges.The conflict-free connection number of a connected graph G,denoted by cf c(G),is defined as the minimum number of colors that are required in order to make G conflict-free connected.In this paper,we investigate the relation between the conflict-free connection number and the independence number of a graph.We firstly show that cf c(G)≤α(G)for any connected graph G,and give an example to show that the bound is sharp.With this result,we prove that if T is a tree with?(T)≥(α(T)+2)/2,then cf c(T)=?(T).     

Acyclic improper colouring of graphs with maximum degree 4

A k-colouring(not necessarily proper) of vertices of a graph is called acyclic, if for every pair of distinct colours i and j the subgraph induced by the edges whose endpoints have colours i and j is acyclic. We consider acyclic k-colourings such that each colour class induces a graph with a given(hereditary) property. In particular, we consider acyclic k-colourings in which each colour class induces a graph with maximum degree at most t, which are referred to as acyclic t-improper k-colourings. The acyclic t-improper chromatic number of a graph G is the smallest k for which there exists an acyclic t-improper k-colouring of G. We focus on acyclic colourings of graphs with maximum degree 4. We prove that 3 is an upper bound for the acyclic 3-improper chromatic number of this class of graphs. We also provide a non-trivial family of graphs with maximum degree4 whose acyclic 3-improper chromatic number is at most 2, namely, the graphs with maximum average degree at most 3. Finally, we prove that any graph G with Δ(G) 4 can be acyclically coloured with 4 colours in such a way that each colour class induces an acyclic graph with maximum degree at most 3.     

Incidence Coloring of Outer-1-planar Graphs

A graph is outer-1-planar if it can be drawn in the plane so that all vertices lie on the outer-face and each edge crosses at most one another edge.It is known that every outer-1-planar graph is a planar partial3-tree.In this paper,we conjecture that every planar graph G has a proper incidence(Δ(G)+2)-coloring and confirm it for outer-1-planar graphs with maximum degree at least 8 or with girth at least 4.Specifically,we prove that every outer-1-planar graph G has an incidence(Δ(G)+3,2)-coloring...     

On the Edge-forwarding Indices of Frobenius Graphs

A G-Frobenius graph F, as defined by Fang, Li, and Praeger, is a connected orbital graph of a Frobenius group G = K × H with Frobenius kernel K and Frobenius complement H. F is also shown to be a Cayley graph, F = Cay（K, S） for K and some subset S of the group K. On the other hand, a network N with a routing function R, written as （N, R）, is an undirected graph N together with a routing R which consists of a collection of simple paths connecting every pair of vertices in the graph. The edge-forwarding index π（N） of a network （N, R）, defined by Heydemann, Meyer, and Sotteau, is a parameter to describe tile maximum load of edges of N. In this paper, we study the edge-forwarding indices of Frobenius graphs. In particular, we obtain the edge-forwarding index of a G-Frobenius graph F with rank（G） ≤ 50.     

A result on quasi k-connected graphs

Let G be a k-connected graph, and T be a subset of V(G)If G- T is not connected,then T is said to be a cut-set of GA k-cut-set T of G is a cut-set of G with |T | = kLet T be a k-cut-set of a k-connected graph GIf G- T can be partitioned into subgraphs G1 and G2 such that |G1| ≥ 2, |G2| ≥ 2, then we call T a nontrivial k-cut-set of GSuppose that G is a(k- 1)-connected graph without nontrivial(k- 1)-cut-setThen we call G a quasi k-connected graphIn this paper, we prove that for any integer k ≥ 5, if G is a k-connected graph without K-4, then every vertex of G is incident with an edge whose contraction yields a quasi k-connected graph, and so there are at least|V(G)|2edges of G such that the contraction of every member of them results in a quasi k-connected graph.     

Unique factorization of compositive hereditary graph properties

A graph property is any class of graphs that is closed under isomorphisms. A graph property P is hereditary if it is closed under taking subgraphs; it is compositive if for any graphs G1, G2 ∈ P there exists a graph G ∈ P containing both G1 and G2 as subgraphs. Let H be any given graph on vertices v1, . . . , vn, n ≥ 2. A graph property P is H-factorizable over the class of graph properties P if there exist P 1 , . . . , P n ∈ P such that P consists of all graphs whose vertex sets can be partitioned into n parts, possibly empty, satisfying: 1. for each i, the graph induced by the i-th non-empty partition part is in P i , and 2. for each i and j with i = j, there is no edge between the i-th and j-th parts if vi and vj are non-adjacent vertices in H. If a graph property P is H-factorizable over P and we know the graph properties P 1 , . . . , P n , then we write P = H [ P 1 , . . . , P n ]. In such a case, the presentation H[ P 1 , . . . , P n ] is called a factorization of P over P. This concept generalizes graph homomorphisms and (P 1 , . . . , P n )-colorings. In this paper, we investigate all H-factorizations of a graph property P over the class of all hered- itary compositive graph properties for finite graphs H. It is shown that in many cases there is exactly one such factorization.     

A conjecture on k-factor-critical and 3-γ-critical graphs

For a graph G =(V,E),a subset VS is a dominating set if every vertex in V is either in S or is adjacent to a vertex in S.The domination number γ(G) of G is the minimum order of a dominating set in G.A graph G is said to be domination vertex critical,if γ(G-v) γ(G) for any vertex v in G.A graph G is domination edge critical,if γ(G ∪ e) γ(G) for any edge e ∈/E(G).We call a graph G k-γ-vertex-critical(resp.k-γ-edge-critical) if it is domination vertex critical(resp.domination edge critical) and γ(G) = k.Ananchuen and Plummer posed the conjecture:Let G be a k-connected graph with the minimum degree at least k+1,where k 2 and k≡|V|(mod 2).If G is 3-γ-edge-critical and claw-free,then G is k-factor-critical.In this paper we present a proof to this conjecture,and we also discuss the properties such as connectivity and bicriticality in 3-γ-vertex-critical claw-free graph.     

On 3-colorings of Plane Graphs

In this paper, we prove that if G is a plane graph without 4-, 5- and 7-circuits and without intersecting triangles, then for each face f of degree at most 11, any 3-coloring of the boundary of f can be extended to G. This gives a positive support to a conjecture of Borodin and Raspaud which claims that each plane graph without 5-circuits and intersecting triangles is 3-colorable.     

ON EDGE-HAMILTONIAN PROPERTY OF BI-CAYLEY GRAPHS

Let G be a finite group, and S be a subset of G. The bi-Cayley graph BCay(G, S)of G with respect to S is defined as the bipartite graph with vertex set G × {0, 1} and edge set {(g, 0),(gs, 1)| g ∈ G, s ∈ S}. In this paper, we first provide two interesting results for edge-hamiltonian property of Cayley graphs and bi-Cayley graphs. Next,we investigate the edge-hamiltonian property of Γ = BCay(G, S), and prove that Γis hamiltonian if and only if Γ is edge-hamiltonian when Γ is a connected bi-Cayley graph.     

Acyclic Edge Coloring of 1-planar Graphs without 4-cycles

An acyclic edge coloring of a graph G is a proper edge coloring such that there are no bichromatic cycles in G.The acyclic chromatic index χ’α(G) of G is the smallest k such that G has an acyclic edge coloring using k colors.It was conjectured that every simple graph G with maximum degree Δ has χ’_α(G) ≤Δ+2.A1-planar graph is a graph that can be drawn in the plane so that each edge is crossed by at most one other edge.In this paper,we show that every 1-planar graph G without 4-cycles h...     

A variation of a conjecture due to Erdös and Sós

Erdoes and Soes conjectured in 1963 that every graph G on n vertices with edge number e（G） 〉 1/2（k - 1）n contains every tree T with k edges as a subgraph. In this paper, we consider a variation of the above conjecture, that is, for n 〉 9/ 2k^2 ＋ 37/2＋ 14 and every graph G on n vertices with e（G） 〉 1/2 （k- 1）n, we prove that there exists a graph G＇ on n vertices having the same degree sequence as G and containing every tree T with k edges as a subgraph.