Monochromatic and Heterochromatic Subgraphs in Edge-Colored Graphs - A Survey

Nowadays the term monochromatic and heterochromatic (or rainbow, multicolored) subgraphs of an edge-colored graph appeared frequently in literature, and many results on this topic have been obtained. In this paper, we survey results on this subject. We classify the results into the following categories: vertex-partitions by monochromatic subgraphs, such as cycles, paths, trees; vertex partition by some kinds of heterochromatic subgraphs; the computational complexity of these partition problems; some kinds of large monochromatic and heterochromatic subgraphs. We have to point out that there are a lot of results on Ramsey type problem of monochromatic and heterochromatic subgraphs. However, it is not our purpose to include them in this survey because this is slightly different from our topics and also contains too large amount of results to deal with together. There are also some interesting results on vertex-colored graphs, but we do not include them, either. Supported by NSFC, PCSIRT and the “973” program.     

Contractible Non-Edges in Triangle-Free Graphs

Thomassen has proved that every triangle-free k-connected graph contains a pair of adjacent vertices whose identification yields again a k-connected graph. We study the existence of a pair of nonadjacent vertices whose identification preserves k-connectivity. In particular, we present a reduction theorem for the class of all bipartite, k-connected graphs. Revised: January 7, 1999     

The Four-in-a-Tree Problem in Triangle-Free Graphs

The three-in-a-tree algorithm of Chudnovsky and Seymour decides in time O(n ⁴) whether three given vertices of a graph belong to an induced tree. Here, we study four-in- a-tree for triangle-free graphs. We give a structural answer to the following question: what does a triangle-free graph look like if no induced tree covers four given vertices? Our main result says that any such graph must have the “same structure”, in a sense to be defined precisely, as a square or a cube. We provide an O(nm)-time algorithm that given a triangle-free graph G together with four vertices outputs either an induced tree that contains them or a partition of V(G) certifying that no such tree exists. We prove that the problem of deciding whether there exists a tree T covering the four vertices such that at most one vertex of T has degree at least 3 is NP-complete.     

A Linear Heterochromatic Number of Graphs

Let G=(V(G),E(G)) be a multigraph with multiple loops allowed, and V ₀V(G). We define h(G,V ₀) to be the minimum integer k such that for every edge-colouring of G using exactly k colours, all the edges incident with some vertex in V ₀ receive different colours. In this paper we prove that if each xV ₀ is incident to at least two edges of G, then h(G,V ₀)=(G[V ₀])+|E(G)|–|V ₀|+1 where (G[V ₀]) is the maximum cardinality of a set of mutually disjoint cycles (of length at least two) in the subgraph induced by V ₀. Acknowledgments.We thank the referee for suggesting us a short alternative proof of our main theorem.     

Large Induced Forests in Triangle-Free Planar Graphs

Given a planar graph G, what is the largest subset of vertices of G that induces a forest? Albertson and Berman [2] conjectured that every planar graph has an induced subgraph on at least half of the vertices that is a forest. For bipartite planar graphs, Akiyama and Wanatabe [1] conjectured that there is always an induced forest of size at least 5n/8. Here we prove that every triangle-free (and therefore every bipartite) planar graph on n vertices has an induced forest of size at least (17n+24)/32.     

Note on Group Distance Magic Graphs G[C 4]

A group distance magic labeling or a ${\mathcal{G}}$ -distance magic labeling of a graph G =  (V, E) with ${|V | = n}$ is a bijection f from V to an Abelian group ${\mathcal{G}}$ of order n such that the weight ${w(x) = \sum_{y\in N_G(x)}f(y)}$ of every vertex ${x \in V}$ is equal to the same element ${\mu \in \mathcal{G}}$ , called the magic constant. In this paper we will show that if G is a graph of order n =  2 ^p (2k + 1) for some natural numbers p, k such that ${\deg(v)\equiv c \mod {2^{p+1}}}$ for some constant c for any ${v \in V(G)}$ , then there exists a ${\mathcal{G}}$ -distance magic labeling for any Abelian group ${\mathcal{G}}$ of order 4n for the composition G[C ₄]. Moreover we prove that if ${\mathcal{G}}$ is an arbitrary Abelian group of order 4n such that ${\mathcal{G} \cong \mathbb{Z}_2 \times\mathbb{Z}_2 \times \mathcal{A}}$ for some Abelian group ${\mathcal{A}}$ of order n, then there exists a ${\mathcal{G}}$ -distance magic labeling for any graph G[C ₄], where G is a graph of order n and n is an arbitrary natural number.     

Note on Integer 4-flows in Graphs

Acta Mathematica Sinica, English Series - Let G be a bridgeless graph and C be a circuit in G. To find a shorter circuit cover of G, Fan proposed a conjecture that if G/C admits a nowhere-zero...     

A Note on Groups Associated with 4-Arc-Transitive Cubic Graphs

A cubic (trivalent) graph is said to be 4-arc-transitive ifits automorphism group acts transitively on the 4-arcs of (wherea 4-arc is a sequence v₀, v₁, ... v₄ of vertices of such thatv_i–1 is adjacent to v_i for 1 i 4, and v_i–1 v_i+1for 1 i < 4). In his investigations into graphs of thissort, Biggs defined a family of groups 4⁺(a^m), for m = 3,4,5...,each presented in terms of generators and relations under theadditional assumption that the vertices of a circuit of lengthm are cyclically permuted by some automorphism. In this paperit is shown that whenever m is a proper multiple of 6, the group4⁺(a^m) is infinite. The proof is obtained by constructing transitivepermutation representations of arbitrarily large degree.     

Rainbow Spanning Subgraphs of Small Diameter in Edge-Colored Complete Graphs

Let s(n, t) be the maximum number of colors in an edge-coloring of the complete graph \(K_n\) that has no rainbow spanning subgraph with diameter at most t. We prove \(s(n,t)={\left( {\begin{array}{c}n-2\\ 2\end{array}}\right) }+1\) for \(n,t\ge 3\), while \(s(n,2)={\left( {\begin{array}{c}n-2\\ 2\end{array}}\right) }+\left\lfloor {\frac{n-1}{2}}\right\rfloor \) for \(n\ne 4\) (and \(s(4,2)=2\)).     

A Generalization of Heterochromatic Graphs and f-Chromatic Spanning Forests

In 2006, Suzuki, and Akbari and Alipour independently presented a necessary and sufficient condition for edge-colored graphs to have a heterochromatic spanning tree, where a heterochromatic spanning tree is a spanning tree whose edges have distinct colors. In this paper, we propose f-chromatic graphs as a generalization of heterochromatic graphs. An edge-colored graph is f-chromatic if each color c appears on at most f(c) edges. We also present a necessary and sufficient condition for edge-colored graphs to have an f-chromatic spanning forest with exactly m components. Moreover, using this criterion, we show that a g-chromatic graph G of order n with ${|E(G)| > \binom{n-m}{2}}$ has an f-chromatic spanning forest with exactly m (1 ≤ m ≤ n ? 1) components if ${g(c) \le \frac{|E(G)|}{n-m}f(c)}$ for any color c.     

A Note on Cycle Lengths in Graphs

 We prove that for every c>0 there exists a constant K = K(c) such that every graph G with n vertices and minimum degree at least c n contains a cycle of length t for every even t in the interval [4,e c(G) − K] and every odd t in the interval [K,o c(G) − K], where e c(G) and o c(G) denote the length of the longest even cycle in G and the longest odd cycle in G respectively. We also give a rough estimate of the magnitude of K. Received: July 5, 2000 Final version received: April 17, 2002 2000 Mathematics Subject Classification. 05C38     

A Note on Uniquely lntersectable Graphs

The following conjecture of Alter and Wang is proven. Consider the intersection graph G_n,m,n?2m, determined by the family of all m-element subsets of an n-element set. Then any realization of G_n,m as an intersection graph by a family of sets satisfies |∪_iA_i|?n; and if |∪_iA_i|=n, then F must be the family of all m-element subsets of ∪_iA_i.     

A Note on Almost Regular Graphs

It can easily be seen that a conjecture of Runge does not hold for a class of graphs whose members will be called “almost regular”. This conjecture is replaced by a weaker one, and a classification of almost regular graphs is given.     

A Note on Semi-coloring of Graphs

Semi-coloring is a new type of edge coloring of graphs. In this note, we show that every graph has a semi-coloring. This answers a problem, posed by Daniely and Linial, in affirmative. It implies that every r-regular graph has at least ${\lceil\frac{r}{2}\rceil}$ different {K ₂, C _i | i ≥ 3}-factors.     

A Note on Group Choosability of Graphs with Girth at least 4

In this paper we show that the group choice number of a graph without K ₅-minor or K _3,3-minor with girth at least 4 (resp. 6) is at most 4 (resp. 3) and we conclude that these results hold for the group chromatic number, the choice number and the chromatic number.     

强正则自补图的一个注记

Kotzig put forward a question on strongly-regular self-complementary graphs, that is, for any natural number k, whether there exists a strongly-regular self- complementary graph whose order is 4k 1, where 4k 1=x2 y2, x and y are positive integers; what is the minimum number that made there exist at least two non-isomorphic strongly-regular self-complementary graphs. In this paper, we use two famous lemmas to generalize the existential conditions for strongly-regular self-complementary circular graphs with 4k 1 orders.     

A Note on Lights-Out-Puzzle: Parity-State Graphs

A state of a graph G is an assignment of 0 or 1 to each vertex of G. A move of a state consists of choosing a vertex and then switching the value of the vertex as well as those of its neighbors. Two states are said to be equivalent if one state can be changed to the other by a series of moves. A parity-state graph is defined to be a graph in which two states are equivalent if and only if the numbers of 1’s in the two states have the same parity. We characterize parity-state graphs and present some constructions of parity-state graphs together with applications. Among other things, it is proved that the one-skeleton of the 3-polytope obtained from a simple 3-polytope by cutting off all vertices is a parity-state graph.