Colourings of the cartesian product of graphs and multiplicative Sidon sets

Let F be a family of connected bipartite graphs, each with at least three vertices. A proper vertex colouring of a graph G with no bichromatic subgraph in F is F-free. The F-free chromatic number χ(G,F) of a graph G is the minimum number of colours in an F-free colouring of G. For appropriate choices of F, several well-known types of colourings fit into this framework, including acyclic colourings, star colourings, and distance-2 colourings. This paper studies F-free colourings of the cartesian product of graphs.     

Chromatic Number of Graphs each Path of which is 3-colourable

In his paper “Fruit salad” (mixed for Paul Erdos) Gyárfás has posed the following conjecture: If each path of a graph spans at most 3-chromatic subgraph then the graph is k-colourable (with a constant k, perhaps with k = 4). We will show that these graphs are colourable with 3 · Illg_c ¦V(G)¦? colours for a suitable constant c = 8/7. As a corollary we obtain that every graph G admits a partition of its vertex set V(G) into at most Illg_c ¦V(G)¦? subsets V_i for a suitable constant c = 8/7, such that the components of each induced subgraph G[V_i] are spaned by a path.     

Equitable total coloring of <Emphasis Type="Italic">F</Emphasis><Subscript><Emphasis Type="Italic">n</Emphasis></Subscript> ⋁ <Emphasis Type="Italic">W</Emphasis><Subscript><Emphasis Type="Italic">n</Emphasis></Subscript>

The minimum number of total independent partition sets of V ∪ E of graph G(V,E) is called the total chromatic number of G denoted by χ _t (G). If the difference of the numbers of any two total independent partition sets of V ∪ E is no more than one, then the minimum number of total independent partition sets of V ∪ E is called the equitable total chromatic number of G, denoted by χ _et (G). In this paper, we obtain the equitable total chromatic number of the join graph of fan and wheel with the same order. Supported by the National Natural Science Foundation of China (No. 10771091).     

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.     

A decomposition for strongly perfect graphs

A graph G is strongly perfect if every induced subgraph H of G contains a stable set that meets all the maximal cliques of H. We present a graph decomposition that preserves strong perfection: more precisely, a stitch decomposition of a graph G = (V, E) is a partition of V into nonempty disjoint subsets V₁, V₂ such that in every P₄ with vertices in both V_iapos;s, each of the three edges has an endpoint in V₁ and the other in V₂. We give a good characterization of graphs that admit a stitch decomposition and establish several results concerning the stitch decomposition of strongly perfect graphs.     

Vertex Set Partitions Preserving Conservativeness

Let G be an undirected graph and ={X₁, …, X_n} be a partition of V(G). Denote by G/ the graph which has vertex set {X₁, …, X_n}, edge set E, and is obtained from G by identifying vertices in each class X_i of the partition . Given a conservative graph (G, w), we study vertex set partitions preserving conservativeness, i.e., those for which (G/ , w) is also a conservative graph. We characterize the conservative graphs (G/ , w), where is a terminal partition of V(G) (a partition preserving conservativeness which is not a refinement of any other partition of this kind). We prove that many conservative graphs admit terminal partitions with some additional properties. The results obtained are then used in new unified short proofs for a co-NP characterization of Seymour graphs by A. A. Ageev, A. V. Kostochka, and Z. Szigeti (1997, J. Graph Theory34, 357–364), a theorem of E. Korach and M. Penn (1992, Math. Programming55, 183–191), a theorem of E. Korach (1994, J. Combin. Theory Ser. B62, 1–10), and a theorem of A. V. Kostochka (1994, in “Discrete Analysis and Operations Research. Mathematics and its Applications (A. D. Korshunov, Ed.), Vol. 355, pp. 109–123, Kluwer Academic, Dordrecht).     

Unique and faithful embeddings of projective-planar graphs

A graph G is uniquely embeddable in a surface F² if for any two embeddings f₁,f₂: G → F², there exists an isomorphism σ: G → G and a homeomorphism h: F² → F² for which h → f₁ = f₂ σ. A graph G is faithfully embeddable in a surface F² if G admits an embedding f: G → F² such that for any isomorphism σ: G → G, there is a homeomorphism h: F² → F² with h → f = f → σ. It will be shown that if a projective-planar graph G is 5-connected and contains a subdivision of the complete graph K₆ as its subgraph, then G is uniquely embeddable in a projective plane, and that moreover if G is not isomorphic to K₆, then G is faithfully embeddable in a projective plane.     

Rotation numers for complete bipartite graphs

A rooted graph is a pair (G, x) where G is a simple undirected graph and x ? V(G). If G if rooted at x, then its rotation number h(G, x) is teh minimum number of edges in a graph F, of the same order as G, such that for all v ? V(F) we can find a copy of G in F with the root x at v. Rotation numbers for complete bipartite graphs were itroduced in [4] by Cockayne and Lorimer. Several cases were evaluated by Bollobás and Cockayne in [2], and in this paper we give a full solution.     

Linear and 2-Frugal Choosability of Graphs of Small Maximum Average Degree

A proper vertex colouring of a graph G is 2-frugal (resp. linear) if the graph induced by the vertices of any two colour classes is of maximum degree 2 (resp. is a forest of paths). A graph G is 2-frugally (resp. linearly) L-colourable if for a given list assignment L:V(G)? 2^{\mathbb N}{L:V(G)\mapsto 2^{\mathbb N}} , there exists a 2-frugal (resp. linear) colouring c of G such that c(v) ? L(v){c(v) \in L(v)} for all v ? V(G){v\in V(G)} . If G is 2-frugally (resp. linearly) L-list colourable for any list assignment such that |L(v)| ≥ k for all v ? V(G){v\in V(G)}, then G is 2-frugally (resp. linearly) k-choosable. In this paper, we improve some bounds on the 2-frugal choosability and linear choosability of graphs with small maximum average degree.     

[a,b]-factorization of a graph

Let a and b be integers such that 0 ? a ? b. Then a graph G is called an [a, b]-graph if a ? d_G(x) ? b for every x ? V(G), and an [a, b]-factor of a graph is defined to be its spanning subgraph F such that a ? d_F(x) ? b for every vertex x, where d_G(x) and d_F(x) denote the degrees of x in G and F, respectively. If the edges of a graph can be decomposed into [a.b]-factors then we say that the graph is [2a, 2a]-factorable. We prove the following two theorems: (i) a graph G is [2a, 2b)-factorable if and only if G is a [2am,2bm]-graph for some integer m, and (ii) every [8m + 2k, 10m + 2k]-graph is [1,2]-factorable.     

Some topics in cochromatic theory

GivenG, a graph, the cochromatic number,Z(G), ofG is the fewest number of sets into which the vertex set can be partitioned so that each set induces a complete or an empty graph. A graph is critically cochromatic if the removal of any of its vertices decreases its cochromatic number. A graph is uniquely cochromatic if there is exactly one partition of minimum order in which each set induces a complete or an empty graph. A graph is comaximal if the removal of any edge increases its cochromatic number. These and related concepts are examined.     

On 2‐factors of a bipartite graph

In this article, we consider the following problem: Given a bipartite graph G and a positive integer k, when does G have a 2‐factor with exactly k components? We will prove that if G = (V₁, V₂, E) is a bipartite graph with |V₁| = |V₂| = n ≥ 2k + 1 and δ (G) ≥ ⌈n/2⌉ + 1, then G contains a 2‐factor with exactly k components. We conjecture that if G = (V₁, V₂; E) is a bipartite graph such that |V₁| = |V₂| = n ≥ 2 and δ (G) ≥ ⌈n/2⌉ + 1, then, for any bipartite graph H = (U₁, U₂; F) with |U₁| ≤ n, |U₂| ≤ n and Δ (H) ≤ 2, G contains a subgraph isomorphic to H. © 1999 John Wiley & Sons, Inc. J Graph Theory 31: 101–106, 1999     

Star partitions of graphs

Let G be a graph and n ≥ 2 an integer. We prove that the following are equivalent: (i) there is a partition (V₁,…,V_m) of V (G) such that each V_i induces one of stars K_1,1,…,K_1,n, and (ii) for every subset S of V(G), G\ S has at most n|S| components with the property that each of their blocks is an odd order complete graph. © 1997 John Wiley & Sons, Inc. J Graph Theory 25: 185–190, 1997     

K4−‐factor in a graph

Let G be a graph of order 4k and let δ(G) denote the minimum degree of G. Let F be a given connected graph. Suppose that |V(G)| is a multiple of |V(F)|. A spanning subgraph of G is called an F‐factor if its components are all isomorphic to F. In this paper, we prove that if δ(G)≥5/2k, then G contains a K₄^?‐factor (K₄^? is the graph obtained from K₄ by deleting just one edge). The condition on the minimum degree is best possible in a sense. In addition, the proof can be made algorithmic. © 2002 John Wiley & Sons, Inc. J Graph Theory 39: 111–128, 2002     

On the computational complexity of ordered subgraph recognition

Let (G, <) be a finite graph G with a linearly ordered vertex set V. We consider the decision problem (G, <)ORD to have as an instance an (unordered) graph Γ and as a question whether there exists a linear order ≤ on V(Γ) and an order preserving graph isomorphism of (G, <) onto an induced subgraph of Γ. Several familiar classes of graph are characterized as the yes-instances of (G, < )ORD for appropriate choices of (G, <). Here the complexity of (G, <)ORD is investigated. We conjecture that for any 2-connected graph G, G ≠ K_k, (G, <)ORD is NP-complete. This is verified for almost all 2-connected graphs. Several related problems are formulated and discussed. © 1995 John Wiley & Sons, Inc.     

Existence of subgraph with orthogonal (g,f)-factorization

Simple graphs are considered. Let G be a graph andg(x) andf(x) integer-valued functions defined on V(G) withg(x)⩽f(x) for everyxɛV(G). For a subgraphH ofG and a factorizationF=|F ₁,F ₂,⃛,F ₁| ofG, if |E(H)∩E(F ₁)|=1,1⩽i⩽j, then we say thatF orthogonal toH. It is proved that for an (mg(x)+k,mf(x) -k)-graphG, there exists a subgraphR ofG such that for any subgraphH ofG with |E(H)|=k,R has a (g,f)-factorization orthogonal toH, where 1⩽k<m andg(x)⩾1 orf(x)⩾5 for everyxɛV(G). Project supported by the Chitia Postdoctoral Science Foundation and Chuang Xin Foundation of the Chinese Academy of Sciences.     

Graph colourings with forbidden k-coloured subgraphs

Abstract

For a set F of graphs and a natural number k, an (F, k)-colouring of a graph G is a proper colouring of V (G) such that no subgraph of G isomorphic to an element of F is coloured with at most k colours. Equivalently, if P is the class of all graphs that do not contain an element of F as a subgraph, a χP,k colouring of G is a proper colouring such that the union of at most k colour classes induces a graph in P. The smallest number of colours in such a colouring of G, if it exists, is denoted by χP,k (G). We give some general results on χP,k-colourings and investigate values of χP,k (G) for some choices of P and classes of graphs G.     

Path factors of bipartite graphs

A path on n vertices is denoted by P_n. For any graph H, the number of isolated vertices of H is denoted by i(H). Let G be a graph. A spanning subgraph F of G is called a {P₃, P₄, P₅}-factor of G if every component of F is one of P₃, P₄, and P₅. In this paper, we prove that a bipartite graph G has a {P₃, P₄, P₅}-factor if and only if i(G ? S ? M) ≦ 2|S| + |M| for all S ? V(G) and independent M ? E(G).     

Equipartite graphs

A graph G of even order is weakly equipartite if for any partition of its vertex set into subsets V ₁ and V ₂ of equal size the induced subgraphs G[V ₁] and G[V ₂] are isomorphic. A complete characterization of (weakly) equipartite graphs is derived. In particular, we show that each such graph is vertex-transitive. In a subsequent paper, we use these results to characterize equipartite polytopes, a geometric analogue of equipartite graphs. Supported by Research Plan MSM 4977751301 of the Czech Ministry of Education. The Institute for Theoretical Computer Science is supported by Czech Ministry of Education as projects LN00A056 and 1M0545. Support by the Fulbright Senior Specialist Program for his stay in Pilsen in summer 2003 is acknowleged.     

Graph equations for line graphs,total graphs,middle graphs and quasi-total graphs

Let G be a graph with vertex-set V(G) and edge-set X(G). Let L(G) and T(G) denote the line graph and total graph of G. The middle graph M(G) of G is an intersection graph Ω(F) on the vertex-set V(G) of any graph G. Let F = V′(G) ∪ X(G) where V′(G) indicates the family of all one-point subsets of the set V(G), then $\text{M(G) = Ω(F)}$.The quasi-total graph P(G) of G is a graph with vertex-set V(G)∪X(G) and two vertices are adjacent if and only if they correspond to two non-adjacent vertices of G or to two adjacent edges of G or to a vertex and an edge incident to it in G.In this paper we solve graph equations $\text{L(G) ? P(H);}\text{L(G)}\text{? P(H); P(G) ? T(H);}\text{P(G)}\text{? T(H); M(G) ? P(H);}\text{M(G)}\text{? P(H)}$.