Polyhedral results on the stable set problem in graphs containing even or odd pairs

Mathematical Programming - Even and odd pairs are important tools in the study of perfect graphs and were instrumental in the proof of the Strong Perfect Graph Theorem. We suggest that such pairs...     

On classes of minimal circular-imperfect graphs

Circular-perfect graphs form a natural superclass of perfect graphs: on the one hand due to their definition by means of a more general coloring concept, on the other hand as an important class of χ-bound graphs with the smallest non-trivial χ-binding function χ(G)?ω(G)+1.The Strong Perfect Graph Conjecture, recently settled by Chudnovsky et al. [The strong perfect graph theorem, Ann. of Math. 164 (2006) 51-229], provides a characterization of perfect graphs by means of forbidden subgraphs. It is, therefore, natural to ask for an analogous conjecture for circular-perfect graphs, that is for a characterization of all minimal circular-imperfect graphs.At present, not many minimal circular-imperfect graphs are known. This paper studies the circular-(im)perfection of some families of graphs: normalized circular cliques, partitionable graphs, planar graphs, and complete joins. We thereby exhibit classes of minimal circular-imperfect graphs, namely, certain partitionable webs, a subclass of planar graphs, and odd wheels and odd antiwheels. As those classes appear to be very different from a structural point of view, we infer that formulating an appropriate conjecture for circular-perfect graphs, as analogue to the Strong Perfect Graph Theorem, seems to be difficult.     

Ferrers digraphs and threshold graphs

We deduce a set of known characterizations of threshold graphs (Theorem 3) from a set of characterizations of Ferrers digraphs (Theorem 1) by investigating the connection between symmetric Ferrers digraphs and threshold graphs. A direct proof of Theorem 3 is easier than the one provided in here, but the purpose of this paper is to view Theorem 1 as an extension of Theorem 3 to the directed case (this extension point of view still holds on an algorithmic ground).     

On the genus of five- and six-regular graphs

This paper shows how to construct infinitely many regular graphs of degrees five and six having given genus γ > 0, which settles favorably Conjecture 1 stated by T. W. Tucker. Tucker has shown that there are infinitely many regular graphs of degrees four and three of arbitrary given genus (Theorem 1). He also proved that the number of regular graphs of degree greater than six embeddable in a given surface is finite (Corollary to Proposition 1). The case of the regular graphs of degrees six and five was left unanswered (Conjecture 1). This paper also shows a new way of constructing infinitely many regular graphs of degrees three and four of arbitrary genus γ > 0.     

The Strong Perfect Graph Conjecture: 40 years of attempts, and its resolution

The Strong Perfect Graph Conjecture (SPGC) was certainly one of the most challenging conjectures in graph theory. During more than four decades, numerous attempts were made to solve it, by combinatorial methods, by linear algebraic methods, or by polyhedral methods. The first of these three approaches yielded the first (and to date only) proof of the SPGC; the other two remain promising to consider in attempting an alternative proof.This paper is an unbalanced survey of the attempts to solve the SPGC; unbalanced, because (1) we devote a significant part of it to the ‘primitive graphs and structural faults’ paradigm which led to the Strong Perfect Graph Theorem (SPGT); (2) we briefly present the other “direct” attempts, that is, those for which results exist showing one (possible) way to the proof; (3) we ignore entirely the “indirect” approaches whose aim was to get more information about the properties and structure of perfect graphs, without a direct impact on the SPGC.Our aim in this paper is to trace the path that led to the proof of the SPGT as completely as possible. Of course, this implies large overlaps with the recent book on perfect graphs [J.L. Ramirez-Alfonsin, B.A. Reed (Eds.), Perfect Graphs, Wiley & Sons, 2001], but it also implies a deeper analysis (with additional results) and another viewpoint on the topic.     

Joins of n-degenerate graphs and uniquely (m,n)-partitionable graphs

The Lick-White point-partition numbers generalize the chromatic number and the point-arboricity. Similarly, uniquely (m, n)-partitionable graphs generalize uniquely m-colorable graphs.Theorem 1 gives a method for constructing uniquely (m, n)-partitionable graphs as well as a sufficient condition for a join of mn-degenerate graphs to be uniquely (m, n)-partitionable. For the case n = 1, we obtain a necessary and sufficient condition (Lemma 1). As a consequence, an embedding result for uniquely (m, 1)-partitionable graphs is obtained (Theorem 2). Finally, uniquely (m, n)-partitionable graphs with minimal connectivity are constructed (Theorem 3).     

Claw-free graphs with strongly perfect complements. Fractional and integral version, Part II: Nontrivial strip-structures

Strongly perfect graphs have been studied by several authors (e.g., Berge and Duchet (1984) [1], Ravindra (1984) [7] and Wang (2006) [8]). In a series of two papers, the current paper being the second one, we investigate a fractional relaxation of strong perfection. Motivated by a wireless networking problem, we consider claw-free graphs that are fractionally strongly perfect in the complement. We obtain a forbidden induced subgraph characterization and display graph-theoretic properties of such graphs. It turns out that the forbidden induced subgraphs that characterize claw-free graphs that are fractionally strongly perfect in the complement are precisely the cycle of length 6, all cycles of length at least 8, four particular graphs, and a collection of graphs that are constructed by taking two graphs, each a copy of one of three particular graphs, and joining them in a certain way by a path of arbitrary length. Wang (2006) [8] gave a characterization of strongly perfect claw-free graphs. As a corollary of the results in this paper, we obtain a characterization of claw-free graphs whose complements are strongly perfect.     

Claw-free graphs with strongly perfect complements. Fractional and integral version. Part I. Basic graphs

Strongly perfect graphs have been studied by several authors (e.g. Berge and Duchet (1984) [1], Ravindra (1984) [12] and Wang (2006) [14]). In a series of two papers, the current paper being the first one, we investigate a fractional relaxation of strong perfection. Motivated by a wireless networking problem, we consider claw-free graphs that are fractionally strongly perfect in the complement. We obtain a forbidden induced subgraph characterization and display graph-theoretic properties of such graphs. It turns out that the forbidden induced subgraphs that characterize claw-free graphs that are fractionally strongly perfect in the complement are precisely the cycle of length 6, all cycles of length at least 8, four particular graphs, and a collection of graphs that are constructed by taking two graphs, each a copy of one of three particular graphs, and joining them in a certain way by a path of arbitrary length. Wang (2006) [14] gave a characterization of strongly perfect claw-free graphs. As a corollary of the results in this paper, we obtain a characterization of claw-free graphs whose complements are strongly perfect.     

Coloring graphs with crossings

We generalize the Five-Color Theorem by showing that it extends to graphs with two crossings. Furthermore, we show that if a graph has three crossings, but does not contain K₆ as a subgraph, then it is also 5-colorable. We also consider the question of whether the result can be extended to graphs with more crossings.     

ω_(aδ)~ω∪bω_δ形图簇的伴随分解及其补图的色等价性

研究图的伴随分解及其补图的色等价性.采用伴随多项式的性质讨论图的伴随分解式,通过图的伴随分解式确定其补图的色性.证明了形图簇的伴随多项式的分解定理,从上述定理得到了这类图簇的补图的色等价性.结论通过图的伴随分解研究其补图的色等价性,是有效的途径与方法,从图的伴随分解式容易看出其补图的色等价图的结构规律.     

Four classes of perfectly orderable graphs

A graph is called “perfectly orderable” if its vertices can be ordered in such a way that, for each induced subgraph F, a certain “greedy” coloring heuristic delivers an optimal coloring of F. No polynomial-time algorithm to recognize these graphs is known. We present four classes of perfectly orderable graphs: Welsh–Powell perfect graphs, Matula perfect graphs, graphs of Dilworth number at most three, and unions of two threshold graphs. Graphs in each of the first three classes are recognizable in a polynomial time. In every graph that belongs to one of the first two classes, we can find a largest clique and an optimal coloring in a linear time.     

Characterizing degree-sum maximal nonhamiltonian bipartite graphs

In 1963, Moon and Moser gave a bipartite analogue to Ore’s famed theorem on hamiltonian graphs. While the sharpness examples of Ore’s Theorem have been independently characterized in at least four different papers, no similar characterization exists for the Moon–Moser Theorem. In this note, we give such a characterization, consisting of one infinite family and two exceptional graphs of order eight.     

Demonstration simple du theoreme de Kuratowski et de sa forme duale

Consideration of non planar graphs irreducible for edge-constractions gives a simpler proof of the well-known Kuratowski theorem (Theorem 2), from its classical dual form (Theorem 1).     

Embedding topological semigroups in topological groups

In [6] Rothman investigated the problem of embedding a topological semigroup in a topological group. He defined a concept calledProperty F and showed that Property F is a necessary and sufficient condition for embedding a commutative, cancellative topological semigroup in its group of quotients as an open subset. This paper announces a generalization of Rothman’s result by definingProperty E and stating that a completely regular topological semigroup S can be embedded in a topological group by a topological isomorphism if and only if S can be embedded (algebraically) in a group and S has Property E. Property E is defined by first constructing a free topological semigroup (Theorem 1.1). This construction resembles the one in [4] for a free topological group. Full details, examples, and other embedding results will appear elsewhere. Some of the results in this paper were contained in the author’s doctoral dissertation written at Rutgers University under Professor Louis F. McAuley.     

Forbidden induced subgraph characterizations of subclasses and variations of perfect graphs: A survey

A graph is perfect if the chromatic number is equal to the clique number for every induced subgraph of the graph. Perfect graphs were defined by Berge in the sixties. In this survey we present known results about partial characterizations by forbidden induced subgraphs of different graph classes related to perfect graphs. We analyze a variation of perfect graphs, clique-perfect graphs, and two subclasses of perfect graphs, coordinated graphs and balanced graphs.     

IB-homogeneous graphs

The Lachlan-Woodrow Theorem identifies ultrahomogeneous graphs up to isomorphism. Recently, the present author and D. Hartman classified MB-homogeneous graphs up to bimorphism-equivalence. We extend those results in this paper, showing that every IB-homogeneous graph is either ultrahomogeneous or MB-homogeneous, thus classifying IB-homogeneous graphs.     

On the 4-color theorem for signed graphs

Máčajová et al. (2016) defined the chromatic number of a signed graph which coincides for all-positive signed graphs with the chromatic number of unsigned graphs. They conjectured that in this setting, for signed planar graphs four colors are always enough, generalizing thereby The Four Color Theorem. We disprove the conjecture.     

Partitioning Perfect Graphs into Stars

The partition of graphs into “nice” subgraphs is a central algorithmic problem with strong ties to matching theory. We study the partitioning of undirected graphs into same‐size stars, a problem known to be NP‐complete even for the case of stars on three vertices. We perform a thorough computational complexity study of the problem on subclasses of perfect graphs and identify several polynomial‐time solvable cases, for example, on interval graphs and bipartite permutation graphs, and also NP‐complete cases, for example, on grid graphs and chordal graphs.     

A Vizing-type theorem for matching forests

A well-known Theorem of Vizing states that one can colour the edges of a graph by Δ+ colours, such that edges of the same colour form a matching. Here, Δ denotes the maximum degree of a vertex, and the maximum multiplicity of an edge in the graph. An analogue of this Theorem for directed graphs was proved by Frank. It states that one can colour the arcs of a digraph by Δ+ colours, such that arcs of the same colour form a branching. For a digraph, Δ denotes the maximum indegree of a vertex, and the maximum multiplicity of an arc. We prove a common generalization of the above two theorems concerning the colouring of mixed graphs (these are graphs having both directed and undirected edges) in such a way that edges of the same colour form a matching forest.