List Colorings with Distinct List Sizes,the Case of Complete Bipartite Graphs

Let be a function on the vertex set of the graph . The graph G is f‐choosable if for every collection of lists with list sizes specified by f there is a proper coloring using colors from the lists. The sum choice number, , is the minimum of , over all functions f such that G is f‐choosable. It is known (Alon, Surveys in Combinatorics, 1993 (Keele), London Mathematical Society Lecture Note Series, Vol. 187, Cambridge University Press, Cambridge, 1993, pp. 1–33, Random Struct Algor 16 (2000), 364–368) that if G has average degree d, then the usual choice number is at least , so they grow simultaneously. In this article, we show that can be bounded while the minimum degree . Our main tool is to give tight estimates for the sum choice number of the unbalanced complete bipartite graph .     

Circular Chromatic Indices of Regular Graphs

The circular chromatic index of a graph G, written , is the minimum r permitting a function such that whenever e and are adjacent. It is known that for any , there is a 3‐regular simple graph G with . This article proves the following results: Assume is an odd integer. For any , there is an n‐regular simple graph G with . For any , there is an n‐regular multigraph G with .     

Cycle‐Saturated Graphs with Minimum Number of Edges

A graph G is called H‐saturated if it does not contain any copy of H, but for any edge e in the complement of G, the graph contains some H. The minimum size of an n‐vertex H‐saturated graph is denoted by . We prove holds for all , where is a cycle with length k. A graph G is H‐semisaturated if contains more copies of H than G does for . Let be the minimum size of an n‐vertex H‐semisaturated graph. We have We conjecture that our constructions are optimal for . © 2012 Wiley Periodicals, Inc. J. Graph Theory 73: 203–215, 2013     

Large ‐ or ‐Minors in 3‐Connected Graphs

There are numerous results bounding the circumference of certain 3‐connected graphs. There is no good bound on the size of the largest bond (cocircuit) of a 3‐connected graph, however. Oporowski, Oxley, and Thomas (J Combin Theory Ser B 57 (1993), 2, 239–257) proved the following result in 1993. For every positive integer k, there is an integer such that every 3‐connected graph with at least n vertices contains a ‐ or ‐minor. This result implies that the size of the largest bond in a 3‐connected graph grows with the order of the graph. Oporowski et al. obtained a huge function iteratively. In this article, we first improve the above authors' result and provide a significantly smaller and simpler function . We then use the result to obtain a lower bound for the largest bond of a 3‐connected graph by showing that any 3‐connected graph on n vertices has a bond of size at least . In addition, we show the following: Let G be a 3‐connected planar or cubic graph on n vertices. Then for any , G has a ‐minor with , and thus a bond of size at least .     

A Closure for 1‐Hamilton‐Connectedness in Claw‐Free Graphs

A graph G is 1‐Hamilton‐connected if is Hamilton‐connected for every vertex . In the article, we introduce a closure concept for 1‐Hamilton‐connectedness in claw‐free graphs. If is a (new) closure of a claw‐free graph G, then is 1‐Hamilton‐connected if and only if G is 1‐Hamilton‐connected, is the line graph of a multigraph, and for some , is the line graph of a multigraph with at most two triangles or at most one double edge. As applications, we prove that Thomassen's Conjecture (every 4‐connected line graph is hamiltonian) is equivalent to the statement that every 4‐connected claw‐free graph is 1‐Hamilton‐connected, and we present results showing that every 5‐connected claw‐free graph with minimum degree at least 6 is 1‐Hamilton‐connected and that every 4‐connected claw‐free and hourglass‐free graph is 1‐Hamilton‐connected.     

Counterexamples to the List Square Coloring Conjecture

The square G² of a graph G is the graph defined on such that two vertices u and v are adjacent in G² if the distance between u and v in G is at most 2. Let and be the chromatic number and the list chromatic number of a graph H, respectively. A graph H is called chromatic‐choosable if . It is an interesting problem to find graphs that are chromatic‐choosable. Kostochka and Woodall (Choosability conjectures and multicircuits, Discrete Math., 240 (2001), 123–143) conjectured that for every graph G, which is called List Square Coloring Conjecture. In this article, we give infinitely many counter examples to the conjecture. Moreover, we show that the value can be arbitrarily large.     

Face 2‐Colorable Embeddings with Faces of Specified Lengths

Suppose and are arbitrary lists of positive integers. In this article, we determine necessary and sufficient conditions on M and N for the existence of a simple graph G, which admits a face 2‐colorable planar embedding in which the faces of one color have boundary lengths and the faces of the other color have boundary lengths . Such a graph is said to have a planar ‐biembedding. We also determine necessary and sufficient conditions on M and N for the existence of a simple graph G whose edge set can be partitioned into r cycles of lengths and also into t cycles of lengths . Such a graph is said to be ‐decomposable.     

On Rooted Packings,Decompositions, and Factors of Graphs

In this article, we study so‐called rooted packings of rooted graphs. This concept is a mutual generalization of the concepts of a vertex packing and an edge packing of a graph. A rooted graph is a pair , where G is a graph and . Two rooted graphs and are isomorphic if there is an isomorphism of the graphs G and H such that S is the image of T in this isomorphism. A rooted graph is a rooted subgraph of a rooted graph if H is a subgraph of G and . By a rooted ‐packing into a rooted graph we mean a collection of rooted subgraphs of isomorphic to such that the sets of edges are pairwise disjoint and the sets are pairwise disjoint. In this article, we concentrate on studying maximum ‐packings when H is a star. We give a complete classification with respect to the computational complexity status of the problems of finding a maximum ‐packing of a rooted graph when H is a star. The most interesting polynomial case is the case when H is the 2‐edge star and S contains the center of the star only. We prove a min–max theorem for ‐packings in this case.     

Average Degree in Graph Powers

The kth power of a simple graph G, denoted by , is the graph with vertex set where two vertices are adjacent if they are within distance k in G. We are interested in finding lower bounds on the average degree of . Here we prove that if G is connected with minimum degree and , then G⁴ has average degree at least . We also prove that if G is a connected d‐regular graph on n vertices with diameter at least , then the average degree of is at least Both these results are shown to be essentially best possible; the second is best possible even when is arbitrarily large.     

Minors in ‐ Chromatic Graphs,II

Let denote the graph obtained from the complete graph by deleting the edges of some ‐subgraph. The author proved earlier that for each fixed s and , every graph with chromatic number has a minor. This confirmed a partial case of the corresponding conjecture by Woodall and Seymour. In this paper, we show that the statement holds already for much smaller t, namely, for .     

Maximizing H‐Colorings of a Regular Graph

For graphs G and H, a homomorphism from G to H, or H‐coloring of G, is an adjacency preserving map from the vertex set of G to the vertex set of H. Our concern in this article is the maximum number of H‐colorings admitted by an n‐vertex, d‐regular graph, for each H. Specifically, writing for the number of H‐colorings admitted by G, we conjecture that for any simple finite graph H (perhaps with loops) and any simple finite n‐vertex, d‐regular, loopless graph G, we have where is the complete bipartite graph with d vertices in each partition class, and is the complete graph on vertices.Results of Zhao confirm this conjecture for some choices of H for which the maximum is achieved by . Here, we exhibit for the first time infinitely many nontrivial triples for which the conjecture is true and for which the maximum is achieved by .We also give sharp estimates for and in terms of some structural parameters of H. This allows us to characterize those H for which is eventually (for all sufficiently large d) larger than and those for which it is eventually smaller, and to show that this dichotomy covers all nontrivial H. Our estimates also allow us to obtain asymptotic evidence for the conjecture in the following form. For fixed H, for all d‐regular G, we have where as . More precise results are obtained in some special cases.     

Independent Domination in Cubic Graphs

A set S of vertices in a graph G is an independent dominating set of G if S is an independent set and every vertex not in S is adjacent to a vertex in S. The independent domination number of G, denoted by , is the minimum cardinality of an independent dominating set. In this article, we show that if is a connected cubic graph of order n that does not have a subgraph isomorphic to K_{2, 3}, then . As a consequence of our main result, we deduce Reed's important result [Combin Probab Comput 5 (1996), 277–295] that if G is a cubic graph of order n, then , where denotes the domination number of G.     

A Proof of a Conjecture of Ohba

We prove a conjecture of Ohba that says that every graph G on at most vertices satisfies .     

Saturation numbers for families of graph subdivisions

For a family of graphs, a graph G is ‐saturated if G contains no member of as a subgraph, but for any edge in , contains some member of as a subgraph. The minimum number of edges in an ‐saturated graph of order n is denoted . A subdivision of a graph H, or an H‐subdivision, is a graph G obtained from H by replacing the edges of H with internally disjoint paths of arbitrary length. We let denote the family of H‐subdivisions, including H itself. In this paper, we study when H is one of or , obtaining several exact results and bounds. In particular, we determine exactly for and show for n sufficiently large that there exists a constant such that . For we show that will suffice, and that this can be improved slightly depending on the value of . We also give an upper bound on for all t and show that . This provides an interesting contrast to a 1937 result of Wagner (Math Ann, 114 (1937), 570–590), who showed that edge‐maximal graphs without a K₅‐minor have at least edges.     

Improper Coloring of Sparse Graphs with a Given Girth,II: Constructions

A graph G is ‐colorable if can be partitioned into two sets and so that the maximum degree of is at most j and of is at most k. While the problem of verifying whether a graph is (0, 0)‐colorable is easy, the similar problem with in place of (0, 0) is NP‐complete for all nonnegative j and k with . Let denote the supremum of all x such that for some constant every graph G with girth g and for every is ‐colorable. It was proved recently that . In a companion paper, we find the exact value . In this article, we show that increasing g from 5 further on does not increase much. Our constructions show that for every g, . We also find exact values of for all g and all .     

A Reconfigurations Analogue of Brooks' Theorem and Its Consequences

Let G be a simple undirected connected graph on n vertices with maximum degree Δ. Brooks' Theorem states that G has a proper Δ‐coloring unless G is a complete graph, or a cycle with an odd number of vertices. To recolor G is to obtain a new proper coloring by changing the color of one vertex. We show an analogue of Brooks' Theorem by proving that from any k‐coloring, , a Δ‐coloring of G can be obtained by a sequence of recolorings using only the original k colors unless

• – G is a complete graph or a cycle with an odd number of vertices, or
• – , G is Δ‐regular and, for each vertex v in G, no two neighbors of v are colored alike.

We use this result to study the reconfiguration graph of the k‐colorings of G. The vertex set of is the set of all possible k‐colorings of G and two colorings are adjacent if they differ on exactly one vertex. We prove that for , consists of isolated vertices and at most one further component that has diameter . This result enables us to complete both a structural and an algorithmic characterization for reconfigurations of colorings of graphs of bounded maximum degree.     

Identifying Codes in Line Graphs

An identifying code of a graph is a subset of its vertices such that every vertex of the graph is uniquely identified by the set of its neighbors within the code. We study the edge‐identifying code problem, i.e. the identifying code problem in line graphs. If denotes the size of a minimum identifying code of an identifiable graph G, we show that the usual bound , where n denotes the order of G, can be improved to in the class of line graphs. Moreover, this bound is tight. We also prove that the upper bound , where is the line graph of G, holds (with two exceptions). This implies that a conjecture of R. Klasing, A. Kosowski, A. Raspaud, and the first author holds for a subclass of line graphs. Finally, we show that the edge‐identifying code problem is NP‐complete, even for the class of planar bipartite graphs of maximum degree 3 and arbitrarily large girth.     

Facial Nonrepetitive Vertex Coloring of Plane Graphs

A sequence is a repetition. A sequence S is nonrepetitive, if no subsequence of consecutive terms of S is a repetition. Let G be a plane graph. That is, a planar graph with a fixed embedding in the plane. A facial path consists of consecutive vertices on the boundary of a face. A facial nonrepetitive vertex coloring of a plane graph G is a vertex coloring such that the colors assigned to the vertices of any facial path form a nonrepetitive sequence. Let denote the minimum number of colors of a facial nonrepetitive vertex coloring of G. Harant and Jendrol’ conjectured that can be bounded from above by a constant. We prove that for any plane graph G.     

A Hypergraph Version of a Graph Packing Theorem by Bollobás and Eldridge

Two n‐vertex hypergraphs G and H pack, if there is a bijection such that for every edge , the set is not an edge in H. Extending a theorem by Bollobás and Eldridge on graph packing to hypergraphs, we show that if and n‐vertex hypergraphs G and H with with no edges of size 0, 1, and n do not pack, then either

1. one of G and H contains a spanning graph‐star, and each vertex of the other is contained in a graph edge, or
2. one of G and H has edges of size not containing a given vertex, and for every vertex x of the other hypergraph some edge of size does not contain x.

     

Equimatchable Graphs on Surfaces

A graph G is equimatchable if each matching in G is a subset of a maximum‐size matching and it is factor critical if has a perfect matching for each vertex v of G. It is known that any 2‐connected equimatchable graph is either bipartite or factor critical. We prove that for 2‐connected factor‐critical equimatchable graph G the graph is either or for some n for any vertex v of G and any minimal matching M such that is a component of . We use this result to improve the upper bounds on the maximum number of vertices of 2‐connected equimatchable factor‐critical graphs embeddable in the orientable surface of genus g to if and to if . Moreover, for any nonnegative integer g we construct a 2‐connected equimatchable factor‐critical graph with genus g and more than vertices, which establishes that the maximum size of such graphs is . Similar bounds are obtained also for nonorientable surfaces. In the bipartite case for any nonnegative integers g, h, and k we provide a construction of arbitrarily large 2‐connected equimatchable bipartite graphs with orientable genus g, respectively nonorientable genus h, and a genus embedding with face‐width k. Finally, we prove that any d‐degenerate 2‐connected equimatchable factor‐critical graph has at most vertices, where a graph is d‐degenerate if every its induced subgraph contains a vertex of degree at most d.