ContributionsUpper domination and upper irredundance perfect graphs

Let β(G), Γ(G) and IR(G) be the independence number, the upper domination number and the upper irredundance number, respectively. A graph G is calledΓ-perfect if β(H) = Γ(H), for every induced subgraph H of G. A graph G is called IR-perfect if Γ(H) = IR(H), for every induced subgraph H of G. In this paper, we present a characterization of Γ-perfect graphs in terms of a family of forbidden induced subgraphs, and show that the class of Γ-perfect graphs is a subclass of IR-perfect graphs and that the class of absorbantly perfect graphs is a subclass of Γ-perfect graphs. These results imply a number of known theorems on Γ-perfect graphs and IR-perfect graphs. Moreover, we prove a sufficient condition for a graph to be Γ-perfect and IR-perfect which improves a known analogous result.     

Proof of a conjecture on irredundance perfect graphs

Let ir(G) and γ(G) be the irredundance number and the domination number of a graph G, respectively. A graph G is called irredundance perfect if ir(H)=γ(H), for every induced subgraph H of G. In this article we present a result which immediately implies three known conjectures on irredundance perfect graphs. © 2002 Wiley Periodicals, Inc. J Graph Theory 41: 292–306, 2002     

On αrγs(k)-perfect graphs

For some integer k0 and two graph parameters π and τ, a graph G is called πτ(k)-perfect, if π(H)−τ(H)k for every induced subgraph H of G. For r1 let α_r and γ_r denote the r-(distance)-independence and r-(distance)-domination number, respectively. In (J. Graph Theory 32 (1999) 303–310), I. Zverovich gave an ingenious complete characterization of α₁γ₁(k)-perfect graphs in terms of forbidden induced subgraphs. In this paper we study α_rγ_s(k)-perfect graphs for r,s1. We prove several properties of minimal α_rγ_s(k)-imperfect graphs. Generalizing Zverovich's main result in (J. Graph Theory 32 (1999) 303–310), we completely characterize α_2r−1γ_r(k)-perfect graphs for r1. Furthermore, we characterize claw-free α₂γ₂(k)-perfect graphs.     

A characterization of domination perfect graphs

Let γ(G) and i(G) be the domination number and independent domination number of a graph G, respectively. Sumner and Moore [8] define a graph G to be domination perfect if γ(H) = i(H), for every induced subgraph H of G. In this article, we give a finite forbidden induced subgraph characterization of domination perfect graphs. Bollobás and Cockayne [4] proved an inequality relating γ(G) and i(G) for the class of K^1,k -free graphs. It is shown that the same inequality holds for a wider class of graphs.     

Game-perfect graphs

A graph coloring game introduced by Bodlaender (Int J Found Comput Sci 2:133–147, 1991) as coloring construction game is the following. Two players, Alice and Bob, alternately color vertices of a given graph G with a color from a given color set C, so that adjacent vertices receive distinct colors. Alice has the first move. The game ends if no move is possible any more. Alice wins if every vertex of G is colored at the end, otherwise Bob wins. We consider two variants of Bodlaender’s graph coloring game: one (A) in which Alice has the right to have the first move and to miss a turn, the other (B) in which Bob has these rights. These games define the A-game chromatic number resp. the B-game chromatic number of a graph. For such a variant g, a graph G is g-perfect if, for every induced subgraph H of G, the clique number of H equals the g-game chromatic number of H. We determine those graphs for which the game chromatic numbers are 2 and prove that the triangle-free B-perfect graphs are exactly the forests of stars, and the triangle-free A-perfect graphs are exactly the graphs each component of which is a complete bipartite graph or a complete bipartite graph minus one edge or a singleton. From these results we may easily derive the set of triangle-free game-perfect graphs with respect to Bodlaender’s original game. We also determine the B-perfect graphs with clique number 3. As a general result we prove that complements of bipartite graphs are A-perfect.      

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.     

A note on the characterization of domination perfect graphs

A graph G is domination perfect if for each induced subgraph H of G, γ(H) = i(H), where γ and i are a graph's domination number and independent domination number, respectively. Zverovich and Zverovich [3] offered a finite forbidden induced characterization of domination perfect graphs. This characterization is not correct, but the ideas in [3] can be used to weaken the known sufficient conditions for a graph to be domination perfect and to obtain short proofs of some results regarding domination perfect graphs. © 1993 John Wiley & Sons, Inc.     

On minimally b-imperfect graphs

A b-coloring is a coloring of the vertices of a graph such that each color class contains a vertex that has a neighbour in all other color classes. The b-chromatic number of a graph G is the largest integer k such that G admits a b-coloring with k colors. A graph is b-perfect if the b-chromatic number is equal to the chromatic number for every induced subgraph H of G. A graph is minimally b-imperfect if it is not b-perfect and every proper induced subgraph is b-perfect. We give a list of minimally b-imperfect graphs, conjecture that a graph is b-perfect if and only if it does not contain a graph from this list as an induced subgraph, and prove this conjecture for diamond-free graphs, and graphs with chromatic number at most three.     

Rainbow faces in edge‐colored plane graphs

A face of an edge‐colored plane graph is called rainbow if the number of colors used on its edges is equal to its size. The maximum number of colors used in an edge coloring of a connected plane graph Gwith no rainbow face is called the edge‐rainbowness of G. In this paper we prove that the edge‐rainbowness of Gequals the maximum number of edges of a connected bridge face factor H of G, where a bridge face factor H of a plane graph Gis a spanning subgraph H of Gin which every face is incident with a bridge and the interior of any one face f∈F(G) is a subset of the interior of some face f′∈F(H). We also show upper and lower bounds on the edge‐rainbowness of graphs based on edge connectivity, girth of the dual graphs, and other basic graph invariants. Moreover, we present infinite classes of graphs where these equalities are attained. © 2009 Wiley Periodicals, Inc. J Graph Theory 62: 84–99, 2009     

A note on the bichromatic numbers of graphs

For a pair of integers k, l≥0, a graph G is (k, l)‐colorable if its vertices can be partitioned into at most k independent sets and at most l cliques. The bichromatic number χ^b(G) of G is the least integer r such that for all k, l with k+l=r, G is (k, l)‐colorable. The concept of bichromatic numbers simultaneously generalizes the chromatic number χ(G) and the clique covering number θ(G), and is important in studying the speed of hereditary properties and edit distances of graphs. It is easy to see that for every graph G the bichromatic number χ^b(G) is bounded above by χ(G)+θ(G)?1. In this article, we characterize all graphs G for which the upper bound is attained, i.e., χ^b(G)=χ(G)+θ(G)?1. It turns out that all these graphs are cographs and in fact they are the critical graphs with respect to the (k, l)‐colorability of cographs. More specifically, we show that a cograph H is not (k, l)‐colorable if and only if H contains an induced subgraph G with χ(G)=k+1, θ(G)=l+1 and χ^b(G)=k+l+1. © 2010 Wiley Periodicals, Inc. J Graph Theory 65: 263–269, 2010     

k-Bounded classes of dominant-independent perfect graphs

Let α(G), γ(G), and i(G) be the independence number, the domination number, and the independent domination number of a graph G, respectively. For any k ≥ 0, we define the following hereditary classes: αi(k) = {G : α(H) − i(H) ≤ k for every H ∈ ISub(G)}; αγ(k) = {G : α(H) − γ(H) ≤ k for every H ∈ ISub(G)}; and iγ(k) = {G : i(H) − γ(H) ≤ k for every H ∈ ISub(G)}, where ISub(G) is the set of all induced subgraphs of a graph G. In this article, we present a finite forbidden induced subgraph characterization for αi(k) and αγ(k) for any k ≥ 0. We conjecture that iγ(k) also has such a characterization. Up to the present, it is known only for iγ(0) (domination perfect graphs [Zverovich & Zverovich, J Graph Theory 20 (1995), 375–395]). © 1999 John Wiley & Sons, Inc. J Graph Theory 32: 303–310, 1999     

Graphs satisfying inequality θ(G)θ(G)

In this paper, we study the edge clique cover number of squares of graphs. More specifically, we study the inequality θ(G²)θ(G) where θ(G) is the edge clique cover number of a graph G. We show that any graph G with at most θ(G) vertices satisfies the inequality. Among the graphs with more than θ(G) vertices, we find some graphs violating the inequality and show that dually chordal graphs and power-chordal graphs satisfy the inequality. Especially, we give an exact formula computing θ(T²) for a tree T.     

Hall parameters of complete and complete bipartite graphs

Given a graph G, for each υ ∈V(G) let L(υ) be a list assignment to G. The well‐known choice number c(G) is the least integer j such that if |L(υ)| ≥j for all υ ∈V(G), then G has a proper vertex colouring ? with ?(υ) ∈ L (υ) (?υ ∈V(G)). The Hall number h(G) is like the choice number, except that an extra non‐triviality condition, called Hall's condition, has to be satisfied by the list assignment. The edge‐analogue of the Hall number is called the Hall index, h′(G), and the total analogue is called the total Hall number, h″(G), of G. If the stock of colours from which L(υ) is selected is restricted to a set of size k, then the analogous numbers are called k‐restricted, or restricted, Hall parameters, and are denoted by h_k(G), h′_k(G) and h″_k(G). Our main object in this article is to determine, or closely bound, h′(K), h″(K_n), h′(K_m,n) and h′_k(K_m,n). We also answer some hitherto unresolved questions about Hall parameters. We show in particular that there are examples of graphs G with h′(G)?h′(G ? e)>1. We show that there are examples of graphs G and induced subgraphs H with h_k(G)<h_k(H) [this phenomenon cannot occur with unrestricted Hall numbers]. We also give an example of a graph G and an integer k such that h_k(G)<χ(G)<h(G). © 2002 Wiley Periodicals, Inc. J Graph Theory 41: 208–237, 2002     

Acyclic Edge Coloring of Triangle‐Free Planar Graphs

An acyclic edge coloring of a graph is a proper edge coloring such that there are no bichromatic cycles. The acyclic chromatic index of a graph is the minimum number k such that there is an acyclic edge coloring using k colors and is denoted by a′(G). It was conjectured by Alon, Sudakov and Zaks (and much earlier by Fiamcik) that a′(G) ? Δ + 2, where Δ = Δ(G) denotes the maximum degree of the graph. If every induced subgraph H of G satisfies the condition |E(H)| ? 2|V(H)|?1, we say that the graph G satisfies Property A. In this article, we prove that if G satisfies Property A, then a′(G) ? Δ + 3. Triangle‐free planar graphs satisfy Property A. We infer that a′(G) ? Δ + 3, if G is a triangle‐free planar graph. Another class of graph which satisfies Property A is 2‐fold graphs (union of two forests). © 2011 Wiley Periodicals, Inc. J Graph Theory     

Set vertex colorings and joins of graphs

For a nontrivial connected graph G, let c: V (G) → ℕ be a vertex coloring of G where adjacent vertices may be colored the same. For a vertex v of G, the neighborhood color set NC(v) is the set of colors of the neighbors of v. The coloring c is called a set coloring if NC(u) ≠ NC(v) for every pair u, v of adjacent vertices of G. The minimum number of colors required of such a coloring is called the set chromatic number x _s (G). A study is made of the set chromatic number of the join G+H of two graphs G and H. Sharp lower and upper bounds are established for x _s (G + H) in terms of x _s (G), x _s (H), and the clique numbers ω(G) and ω(H).     

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.     

Partial characterizations of coordinated graphs: line graphs and complements of forests

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 is equal to 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 list of minimal forbidden induced subgraphs for the class of coordinated graphs is not known. In this paper, we present a partial result in this direction, that is, we characterize coordinated graphs by minimal forbidden induced subgraphs when the graph is either a line graph, or the complement of a forest. F. Bonomo, F. Soulignac, and G. Sueiro’s research partially supported by UBACyT Grant X184 (Argentina), and CNPq under PROSUL project Proc. 490333/2004-4 (Brazil). The research of G. Durán is partially supported by FONDECyT Grant 1080286 and Millennium Science Institute “Complex Engineering Systems” (Chile), and CNPq under PROSUL project Proc. 490333/2004-4 (Brazil).     

Acyclic edge colorings of graphs

A proper coloring of the edges of a graph G is called acyclic if there is no 2‐colored cycle in G. The acyclic edge chromatic number of G, denoted by a′(G), is the least number of colors in an acyclic edge coloring of G. For certain graphs G, a′(G) ≥ Δ(G) + 2 where Δ(G) is the maximum degree in G. It is known that a′(G) ≤ 16 Δ(G) for any graph G. We prove that there exists a constant c such that a′(G) ≤ Δ(G) + 2 for any graph G whose girth is at least cΔ(G) log Δ(G), and conjecture that this upper bound for a′(G) holds for all graphs G. We also show that a′(G) ≤ Δ + 2 for almost all Δ‐regular graphs. © 2001 John Wiley & Sons, Inc. J Graph Theory 37: 157–167, 2001     

On the b-Coloring of Cographs and <Emphasis Type="Italic">P</Emphasis><Subscript>4</Subscript>-Sparse Graphs

A b-coloring of a graph is a coloring such that every color class admits a vertex adjacent to at least one vertex receiving each of the colors not assigned to it. The b-chromatic number of a graph G, denoted by χ _b (G), is the maximum number t such that G admits a b-coloring with t colors. A graph G is b-continuous if it admits a b-coloring with t colors, for every . We define a graph G to be b-monotonic if χ _b (H ₁) ≥ χ _b (H ₂) for every induced subgraph H ₁ of G, and every induced subgraph H ₂ of H ₁. In this work, we prove that P ₄-sparse graphs (and, in particular, cographs) are b-continuous and b-monotonic. Besides, we describe a dynamic programming algorithm to compute the b-chromatic number in polynomial time within these graph classes. Flavia Bonomo: Partially supported by ANPCyT PICT-2007-00533 and PICT-2007-00518, and UBACyT Grants X069 and X606 (Argentina). Guillermo Durán: Partially supported by FONDECyT Grant 1080286 and Millennium Science Institute “Complex Engineering Systems” (Chile), and ANPCyT PICT-2007-00518 and UBACyT Grant X069 (Argentina). Javier Marenco: Partially supported by ANPCyT PICT-2007-00518 and UBACyT Grant X069 (Argentina).     

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