Triangle-free planar graphs with the smallest independence number

Steinberg and Tovey proved that every -vertex planar triangle-free graph has an independent set of size at least , and described an infinite class of tight examples. We show that all -vertex planar triangle-free graphs except for this one infinite class have independent sets of size at least .     

Arc index of spatial graphs

Bae and Park found an upper bound on the arc index of prime links in terms of the minimal crossing number. In this paper, we extend the definition of the arc presentation to spatial graphs and find an upper bound on the arc index of any spatial graph as where is the minimal crossing number of , is the number of edges, and is the number of bouquet cut-components. This upper bound is lowest possible.     

Fractal graphs

The lexicographic sum of graphs is defined as follows. Let be a graph. With each associate a graph . The lexicographic sum of the graphs over is obtained from by substituting each by . Given distinct , we have all the possible edges in the lexicographic sum between and if , and none otherwise. When all the graphs are isomorphic to some graph , the lexicographic sum of the graphs over is called the lexicographic product of by and is denoted by . We say that a graph is fractal if there exists a graph , with at least two vertices, such that . There is a simple way to construct fractal graphs. Let be a graph with at least two vertices. The graph is defined on the set of functions from to as follows. Given distinct is an edge of if is an edge of , where is the smallest integer such that . The graph is fractal because . We prove that a fractal graph is isomorphic to a lexicographic sum over an induced subgraph of , which is itself fractal.     

The edge-subgraph poset of a graph and the edge reconstruction conjecture

We consider only finite simple graphs in this paper. Earlier we showed that many invariants of a graph can be computed from the isomorphism class of its partially ordered set of distinct unlabeled non-empty induced subgraphs, that is, the subgraphs themselves are not required. In this paper, we consider an analogous problem of reconstructing an arbitrary graph up to isomorphism from its abstract edge-subgraph poset , which we call the -reconstruction problem. We present an infinite family of graphs that are not -reconstructible and show that the edge reconstruction conjecture is true if and only if the graphs in the family are the only graphs that are not -reconstructible. Let be the set of all unlabeled graphs. Let denote the number of homomorphisms from to . Let be a bijection such that for all , we have . We conjecture that is the identity map. Our conjecture is motivated by the homomorphism cancellation results of Lovász. We prove that the conjecture stated above is weaker than the edge reconstruction conjecture.     

Partitioning a graph into monochromatic connected subgraphs

We show that every -edge-colored graph on vertices with minimum degree at least can be partitioned into two monochromatic connected subgraphs, provided is sufficiently large. This minimum degree condition is tight and the result proves a conjecture of Bal and DeBiasio. We also make progress on another conjecture of Bal and DeBiasio on covering graphs with large minimum degree with monochromatic components of distinct colors.     

Edge clique cover of claw-free graphs

The smallest number of cliques, covering all edges of a graph , is called the (edge) clique cover number of and is denoted by . It is an easy observation that if is a line graph on vertices, then . G. Chen et al. [Discrete Math. 219 (2000), no. 1–3, 17–26; MR1761707] extended this observation to all quasi-line graphs and questioned if the same assertion holds for all claw-free graphs. In this paper, using the celebrated structure theorem of claw-free graphs due to Chudnovsky and Seymour, we give an affirmative answer to this question for all claw-free graphs with independence number at least three. In particular, we prove that if is a connected claw-free graph on vertices with three pairwise nonadjacent vertices, then and the equality holds if and only if is either the graph of icosahedron, or the complement of a graph on vertices called “twister” or the power of the cycle , for some positive integer .     

On perfect matchings in matching covered graphs

A graph is matching-covered if every edge of is contained in a perfect matching. A matching-covered graph is strongly coverable if, for any edge of , the subgraph is still matching-covered. An edge subset of a matching-covered graph is feasible if there exist two perfect matchings and such that , and an edge subset with at least two edges is an equivalent set if a perfect matching of contains either all edges in or none of them. A strongly matchable graph does not have an equivalent set, and any two independent edges of form a feasible set. In this paper, we show that for every integer , there exist infinitely many -regular graphs of class 1 with an arbitrarily large equivalent set that is not switching-equivalent to either or , which provides a negative answer to a problem of Lukot’ka and Rollová. For a matching-covered bipartite graph , we show that has an equivalent set if and only if it has a 2-edge-cut that separates into two balanced subgraphs, and is strongly coverable if and only if every edge-cut separating into two balanced subgraphs and satisfies and .     

Improper coloring of graphs on surfaces

A graph is -colorable if its vertex set can be partitioned into sets , such that for each , the subgraph of induced by has maximum degree at most . The Four Color Theorem states that every planar graph is -colorable, and a classical result of Cowen, Cowen, and Woodall shows that every planar graph is -colorable. In this paper, we extend both of these results to graphs on surfaces. Namely, we show that every graph embeddable on a surface of Euler genus is -colorable and -colorable. Moreover, these graphs are also -colorable and -colorable. We also prove that every triangle-free graph that is embeddable on a surface of Euler genus is -colorable. This is an extension of Grötzsch's Theorem, which states that triangle-free planar graphs are -colorable. Finally, we prove that every graph of girth at least 7 that is embeddable on a surface of Euler genus is -colorable. All these results are best possible in several ways as the girth condition is sharp, the constant maximum degrees cannot be improved, and the bounds on the maximum degrees depending on are tight up to a constant multiplicative factor.     

On -connected graphs

A graph is called -connected if is -edge-connected and is -edge-connected for every vertex . The study of -connected graphs is motivated by a theorem of Thomassen [J. Combin. Theory Ser. A 110 (2015), pp. 67–78] (that was a conjecture of Frank [SIAM J. Discrete Math. 5 (1992), no. 1, pp. 25–53]), which states that a graph has a -vertex-connected orientation if and only if it is (2,2)-connected. In this paper, we provide a construction of the family of -connected graphs for even, which generalizes the construction given by Jordán [J. Graph Theory 52 (2006), pp. 217–229] for (2,2)-connected graphs. We also solve the corresponding connectivity augmentation problem: given a graph and an integer , what is the minimum number of edges to be added to make -connected. Both these results are based on a new splitting-off theorem for -connected graphs.     

Online Ramsey theory for a triangle on -free graphs

Given a class of graphs and a fixed graph , the online Ramsey game for H on is a game between two players Builder and Painter as follows: an unbounded set of vertices is given as an initial state, and on each turn Builder introduces a new edge with the constraint that the resulting graph must be in , and Painter colors the new edge either red or blue. Builder wins the game if Painter is forced to make a monochromatic copy of at some point in the game. Otherwise, Painter can avoid creating a monochromatic copy of forever, and we say Painter wins the game. We initiate the study of characterizing the graphs such that for a given graph , Painter wins the online Ramsey game for on -free graphs. We characterize all graphs such that Painter wins the online Ramsey game for on the class of -free graphs, except when is one particular graph. We also show that Painter wins the online Ramsey game for on the class of -minor-free graphs, extending a result by Grytczuk, Hałuszczak, and Kierstead [Electron. J. Combin. 11 (2004), p. 60].     

Filling the complexity gaps for colouring planar and bounded degree graphs

A colouring of a graph is a function such that for every . A -regular list assignment of is a function with domain such that for every , is a subset of of size . A colouring of respects a -regular list assignment of if for every . A graph is -choosable if for every -regular list assignment of , there exists a colouring of that respects . We may also ask if for a given -regular list assignment of a given graph , there exists a colouring of that respects . This yields the -Regular List Colouring problem. For , we determine a family of classes of planar graphs, such that either -Regular List Colouring is -complete for instances with , or every is -choosable. By using known examples of non--choosable and non--choosable graphs, this enables us to classify the complexity of -Regular List Colouring restricted to planar graphs, planar bipartite graphs, planar triangle-free graphs, and planar graphs with no -cycles and no -cycles. We also classify the complexity of -Regular List Colouring and a number of related colouring problems for graphs with bounded maximum degree.     

The average degree of a subcubic edge-chromatic critical graph

A graph is here called 3- critical if , and for every edge of . The 3-critical graphs include (the Petersen graph with a vertex deleted), and subcubic graphs that are Hajós joins of copies of . Building on a recent paper of Cranston and Rabern, it is proved here that if is 3-critical and not nor a Hajós join of two copies of , then has average degree at least ; this bound is sharp, as it is the average degree of a Hajós join of three copies of .     

Counting degree sequences of spanning trees in bipartite graphs: A graph-theoretic proof

Given a bipartite graph with bipartition each spanning tree in has a degree sequence on and one on . Löhne and Rudloff showed that the number of possible degree sequences on equals the number of possible degree sequences on . Their proof uses a non-trivial characterization of degree sequences by -draconian sequences based on polyhedral results of Postnikov. In this paper, we give a purely graph-theoretic proof of their result.     

Polynomial relations between matrices of graphs

We derive a correspondence between the eigenvalues of the adjacency matrix and the signless Laplacian matrix of a graph when is -biregular by using the relation . This motivates asking when it is possible to have for a polynomial, , and matrices associated to a graph . It turns out that, essentially, this can only happen if is either regular or biregular.     

The 1-2-3-conjecture holds for dense graphs

This paper confirms the 1-2-3-conjecture for graphs that can be edge-decomposed into cliques of order at least 3. Furthermore we combine this with a result by Barber, Kühn, Lo, and Osthus to show that there is a constants such that every graph with and , where is the minimum degree of satisfying the 1-2-3-conjecture.     

3-Color bipartite Ramsey number of cycles and paths

The -color bipartite Ramsey number of a bipartite graph is the least integer for which every -edge-colored complete bipartite graph contains a monochromatic copy of . The study of bipartite Ramsey numbers was initiated, over 40 years ago, by Faudree and Schelp and, independently, by Gyárfás and Lehel, who determined the 2-color Ramsey number of paths. In this paper we determine asymptotically the 3-color bipartite Ramsey number of paths and (even) cycles.     

Strong chromatic index of unit distance graphs

The strong chromatic index of a graph , denoted by , is defined as the least number of colors in a coloring of edges of , such that each color class is an induced matching (or: if edges and have the same color, then both vertices of are not adjacent to any vertex of ). A graph is a unit distance graph in if vertices of can be uniquely identified with points in , so that is an edge of if and only if the Euclidean distance between the points identified with and is 1. We would like to find the largest possible value of , where is a unit distance graph (in and ) of maximum degree . We show that , where is a unit distance graph in of maximum degree . We also show that the maximum possible size of a strong clique in unit distance graph in is linear in and give a tighter result for unit distance graphs in the plane.     

Distance matching extension and local structure of graphs

A matching in a graph is said to be extendable if there exists a perfect matching of containing . Also, is said to be a distance matching if the shortest distance between a pair of edges in is at least . A graph is distance matchable if every distance matching is extendable in , regardless of its size. In this paper, we study the class of distance matchable graphs. In particular, we prove that for every integer with , there exists a positive integer such that every connected, locally -connected -free graph of even order is distance matchable. We also prove that every connected, locally -connected -free graph of even order is distance matchable. Furthermore, we make more detailed analysis of -free graphs and study their distance matching extension properties.     

On the clique number of the square of a line graph and its relation to maximum degree of the line graph

In 1985, Erdős and Nešetřil conjectured that the square of the line graph of a graph , that is, , can be colored with colors. This conjecture implies the weaker conjecture that the clique number of such a graph, that is, , is at most . In 2015, Śleszyńska-Nowak proved that . In this paper, we prove that . This theorem follows from our stronger result that where .