On Induced Subgraphs with All Degrees Odd

 Gallai proved that the vertex set of any graph can be partitioned into two sets, each inducing a subgraph with all degrees even. We prove that every connected graph of even order has a vertex partition into sets inducing subgraphs with all degrees odd, and give bounds for the number of sets of this type required for vertex partitions and vertex covers. We also give results on the partitioning and covering problems for random graphs. Received: October 5, 1998?Final version received: October 20, 2000     

有限连通图上随机扩张森林和连通子图的边负相关性

设G为有限连通图．本文研究图G的子图空间G上的三类概率测度,它们分别刻画图的随机扩张树,随机扩张森林和随机连通子图．基于G上均匀扩张树的边负相关性,我们构造G上的一族边负相关的非平凡随机扩张森林和随机连通子图．此外,我们还给出一定条件下图上均匀扩张森林的边负相关性．     

一个不可定向曲面的极小禁用子图的构造

曲面S的一个极小禁用子图是这样的一个图,它的任何一个顶点的度都不小于3,它不能嵌入在S上,但是删去任何一条边后得到的图能嵌入在S上.本文给出了四种构造一个不可定向曲面的极小禁用子图的方式,即粘合一个顶点,一个图的边被其它的图替换,粘合两个顶点,将一个图放在另一个图的一个曲面嵌入的面内.     

On minimal forbidden subgraph characterizations of balanced graphs

A graph is balanced if its clique-matrix contains no edge–vertex incidence matrix of an odd chordless cycle as a submatrix. While a forbidden induced subgraph characterization of balanced graphs is known, there is no such characterization by minimal forbidden induced subgraphs. In this work, we provide minimal forbidden induced subgraph characterizations of balanced graphs restricted to graphs that belong to one of the following graph classes: complements of bipartite graphs, line graphs of multigraphs, and complements of line graphs of multigraphs. These characterizations lead to linear-time recognition algorithms for balanced graphs within the same three graph classes.     

Spanning trees in hyperbolic graphs

We construct spanning trees in locally finite hyperbolic graphs that represent their hyperbolic compactification in a good way: so that the tree has at least one but at most a bounded number of disjoint rays to each boundary point. As a corollary we extend a result of Gromov which says that from every hyperbolic graph with bounded degrees one can construct a tree (disjoint from the graph) with a continuous surjection from the ends of the tree onto the hyperbolic boundary such that the surjection is finite-to-one. We shall construct a tree with these properties as a subgraph of the hyperbolic graph, which in addition is also a spanning tree of that graph.     

Parity vertex colouring of plane graphs

A proper vertex colouring of a 2-connected plane graph G is a parity vertex colouring if for each face f and each colour c, either no vertex or an odd number of vertices incident with f is coloured with c. The minimum number of colours used in such a colouring of G is denoted by χ_p(G).In this paper, we prove that χ_p(G)≤118 for every 2-connected plane graph G.     

Hamiltonian arcs in infinite self-complementary graphs

An infinite self-complementary (s.c.) graph is quasi-locally-finite if, for each vertex ξ, either the number of vertices adjacent to ξ is finite or the number of vertices not adjacent to ξ is finite. We prove that every quasi-locally-finite s.c. graph has a spanning subgraph consisting of two 1-way infinite arcs, and give an example of a countable s.c. graph (not quasi-locally-finite) which requires infinitely many 1-way infinite arcs for a spanning subgraph.     

Regular pseudo-median graphs

A graph is pseudo-median if for every triple u, v, w of vertices there exists either a unique vertex between each pair of them (if their mutual distances sum up to an even number) or a unique triangle whose edges lie between the three pairs of u, v, w, respectively (if the distance sum is odd). We show that a finite pseudo-median graph is regular if and only if it is the Cartesian product of a hypercube with either a complete graph or a hyper-octahedron. Every self-map of a pseudo-median graph that preserves or collapses edges has an invariant regular pseudo-median subgraph. Furthermore, the set of all vertices minimizing the total distance to the vertices of a pseudo-median graph induces a regular pseudo-median subgraph.     

Maximum Δ‐edge‐colorable subgraphs of class II graphs

A graph G is class II, if its chromatic index is at least Δ + 1. Let H be a maximum Δ‐edge‐colorable subgraph of G. The paper proves best possible lower bounds for |E(H)|/|E(G)|, and structural properties of maximum Δ‐edge‐colorable subgraphs. It is shown that every set of vertex‐disjoint cycles of a class II graph with Δ≥3 can be extended to a maximum Δ‐edge‐colorable subgraph. Simple graphs have a maximum Δ‐edge‐colorable subgraph such that the complement is a matching. Furthermore, a maximum Δ‐edge‐colorable subgraph of a simple graph is always class I. © 2011 Wiley Periodicals, Inc. J Graph Theory     

以子图为根的k距局部子图的可重构性

本文定义了图中以某个图为根的k距局部子图，证明了图中同构于上述 k距局部子图的子图的数目是可重构的，从而给出了一个新结果并推广了文献^[5]中的定理。     

Probabilistic qualification of attack in abstract argumentation

An argument graph is a graph where each node denotes an argument, and each arc denotes an attack by one argument on another. It offers a valuable starting point for theoretical analysis of argumentation following the proposals by Dung. However, the definition of an argument graph does not take into account the belief in the attacks. In particular, when constructing an argument graph from informal arguments, where each argument is described in free text, it is often evident that there is uncertainty about whether some of the attacks hold. This might be because there is some expressed doubt that an attack holds or because there is some imprecision in the language used in the arguments. In this paper, we use the set of spanning subgraphs of an argument graph as a sample space. A spanning subgraph contains all the arguments, and a subset of the attacks, of the argument graph. We assign a probability value to each spanning subgraph such that the sum of the assignments is 1. This means we can reflect the uncertainty over which is the actual subgraph using this probability distribution. Using the probability distribution over subgraphs, we can then determine the probability that a set of arguments is admissible or an extension. We can also obtain the probability of an attack relationship in the original argument graph as a marginal distribution (i.e. it is the sum of the probability assigned to each subgraph containing that attack relationship). We investigate some of the features of this proposal, and we consider the utility of our framework for capturing some practical argumentation scenarios.     

Partial characterizations of clique-perfect and coordinated graphs: superclasses of triangle-free graphs

A graph is clique-perfect if the cardinality of a maximum clique-independent set equals the cardinality of a minimum clique-transversal, for all its induced subgraphs. A graph G is coordinated if the chromatic number of the clique graph of H equals the maximum number of cliques of H with a common vertex, for every induced subgraph H of G. Coordinated graphs are a subclass of perfect graphs. The complete lists of minimal forbidden induced subgraphs for the classes of cliqueperfect and coordinated graphs are not known, but some partial characterizations have been obtained. In this paper, we characterize clique-perfect and coordinated graphs by minimal forbidden induced subgraphs when the graph is either paw-free or {gem,W₄,bull}-free, two superclasses of triangle-free graphs.     

Even Factors of Large Size

An even factor of a graph is a spanning subgraph in which each vertex has a positive even degree. We show that if a simple graph admits an even factor, then one of its even factors has at least edges.     

A characterization of level planar graphs

We present a characterization of level planar graphs in terms of minimal forbidden subgraphs called minimal level non-planar (MLNP) subgraph patterns. We show that an MLNP subgraph pattern is completely characterized by either a tree, a level non-planar cycle or a level planar cycle with certain path augmentations.     

Bounded degree acyclic decompositions of digraphs

An acyclic decomposition of a digraph is a partition of the edges into acyclic subgraphs. Trivially every digraph has an acyclic decomposition into two subgraphs. It is proved that for every integer s2 every digraph has an acyclic decomposition into s subgraphs such that in each subgraph the outdegree of each vertex v is at most . For all digraphs this degree bound is optimal.     

ON THE MINIMUM FEASIBLE GRAPH FOR FOUR SETS

ＯＮＴＨＥＭＩＮＩＭＵＭＦＥＡＳＩＢＬＥＧＲＡＰＨＦＯＲＦＯＵＲＳＥＴＳＸＵＹＩＮＦＥＮＧＡＮＤＦＵＸＩＡＯＢＩＮＧＡｂｓｔｒａｃｔ：ＧｉｖｅｎａｃｏｍｐｌｅｔｅｇｒａｐｈｗｉｔｈｖｅｒｔｅｘｓｅｔＸａｎｄｓｕｂｓｅｔｓＸ＿１，Ｘ＿２，．．．，Ｘ＿ｎ...     

Partial characterizations of clique-perfect and coordinated graphs: Superclasses of triangle-free graphs

A graph G is clique-perfect if the cardinality of a maximum clique-independent set of H equals the cardinality of a minimum clique-transversal of H, for every induced subgraph H of G. A graph G is coordinated if the minimum number of colors that can be assigned to the cliques of H in such a way that no two cliques with non-empty intersection receive the same color equals the maximum number of cliques of H with a common vertex, for every induced subgraph H of G. Coordinated graphs are a subclass of perfect graphs. The complete lists of minimal forbidden induced subgraphs for the classes of clique-perfect and coordinated graphs are not known, but some partial characterizations have been obtained. In this paper, we characterize clique-perfect and coordinated graphs by minimal forbidden induced subgraphs when the graph is either paw-free or {gem, W₄, bull}-free, both superclasses of triangle-free graphs.     

On b-perfect Chordal Graphs

The b-chromatic number of a graph G is the largest integer k such that G has a coloring of the vertices in k color classes such that every color class contains a vertex that has a neighbour in all other color classes. We characterize the class of chordal graphs for which the b-chromatic number is equal to the chromatic number for every induced subgraph. This research was supported by Algerian-French program CMEP/Tassili 05 MDU 639.     

Minimal configuration trees

A graph is singular of nullity η if zero is an eigenvalue of its adjacency matrix with multiplicity η. If η(G)=1, then the core of G is the subgraph induced by the vertices associated with the non-zero entries of the zero-eigenvector. A connected subgraph of G with the least number of vertices and edges, that has nullity one and the same core as G, is called a minimal configuration. A subdivision of a graph G is obtained by inserting a vertex on every edge of G. We review various properties of minimal configurations. In particular, we show that a minimal configuration is a tree if and only if it is a subdivision of some other tree.     

2-connected coverings of bounded degree in 3-connected graphs

In a recent paper, Barnette showed that every 3-connected planar graph has a 2-connected spanning subgraph of maximum degree at most fifteen, he also constructed a planar triangulation that does not have 2-connected spanning subgraphs of maximum degree five. In this paper, we show that every 3-connected graph which is embeddable in the sphere, the projective plane, the torus or the Klein bottle has a 2-connected spanning subgraph of maximum degree at most six. © 1995 John Wiley & Sons, Inc.