Antimagic labeling and canonical decomposition of graphs

An antimagic labeling of a connected graph with m edges is an injective assignment of labels from {1,…,m} to the edges such that the sums of incident labels are distinct at distinct vertices. Hartsfield and Ringel conjectured that every connected graph other than K₂ has an antimagic labeling. We prove this for the classes of split graphs and graphs decomposable under the canonical decomposition introduced by Tyshkevich. As a consequence, we provide a sufficient condition on graph degree sequences to guarantee an antimagic labeling.     

Hamiltonicity in connected regular graphs

In 1980, Jackson proved that every 2-connected k-regular graph with at most 3k vertices is Hamiltonian. This result has been extended in several papers. In this note, we determine the minimum number of vertices in a connected k-regular graph that is not Hamiltonian, and we also solve the analogous problem for Hamiltonian paths. Further, we characterize the smallest connected k-regular graphs without a Hamiltonian cycle.     

Topological additive numbering of directed acyclic graphs

We propose to study a problem that arises naturally from both Topological Numbering of Directed Acyclic Graphs, and Additive Coloring (also known as Lucky Labeling). Let D be a digraph and f   a labeling of its vertices with positive integers; denote by S(v)$S(v)$ the sum of labels over all neighbors of each vertex v. The labeling f is called topological additive numbering   if S(u)<S(v)$S(u)<S(v)$ for each arc (u,v)$(u,v)$ of the digraph. The problem asks to find the minimum number k for which D   has a topological additive numbering with labels belonging to {1,…,k}$\{1,\dots ,k\}$, denoted by _ηt(D)${\eta }_t(D)$.     

Some optimization problems on weak-bisplit graphs

A new decomposition scheme for bipartite graphs namely canonical decomposition was introduced by Fouquet et al. [Internat. J. Found. Comput. Sci. 10 (1999) 513-533]. The so-called weak-bisplit graphs are totally decomposable following this decomposition. We present here some optimization problems for general bipartite graphs which have efficient solutions when dealing with weak-bisplit graphs.     

A note on 2-facial coloring of plane graphs

An l-facial coloring of a plane graph is a vertex coloring such that any two different vertices joined by a facial walk of length at most l receive distinct colors. It is known that every plane graph admits a 2-facial coloring using 8 colors [D. Král, T. Madaras, R. Škrekovski, Cyclic, diagonal and facial coloring, European J. Combin. 3-4 (26) (2005) 473-490]. We improve this bound for plane graphs with large girth and prove that if G is a plane graph with girth g?14 (resp. 10, 8) then G admits a 2-facial coloring using 5 colors (resp. 6, 7). Moreover, we give exact bounds for outerplanar graphs and K₄-minor free graphs.     

Oriented colorings of 2-outerplanar graphs

A graph G is 2-outerplanar if it has a planar embedding such that the subgraph obtained by removing the vertices of the outer face is outerplanar. The oriented chromatic number of an oriented graph H is defined as the minimum order of an oriented graph H^′ such that H has a homomorphism to H^′. In this paper, we prove that 2-outerplanar graphs are 4-degenerate. We also show that oriented 2-outerplanar graphs have a homomorphism to the Paley tournament QR₆₇, which implies that their (strong) oriented chromatic number is at most 67.     

The 2-dipath chromatic number of Halin graphs

A 2-dipath k-coloring f of an oriented graph is a mapping from to the color set {1,2,…,k} such that f(x)≠f(y) whenever two vertices x and y are linked by a directed path of length 1 or 2. The 2-dipath chromatic number of is the smallest k such that has a 2-dipath k-coloring. In this paper we prove that if is an oriented Halin graph, then . There exist infinitely many oriented Halin graphs such that .     

About acyclic edge colourings of planar graphs

Let G=(V,E) be any finite simple graph. A mapping is called an acyclic edge k-colouring of G, if any two adjacent edges have different colours and there are no bichromatic cycles in G. In other words, for every pair of distinct colours i and j, the subgraph induced by all the edges which have either colour i or j is acyclic. The smallest number k of colours, such that G has an acyclic edge k-colouring is called the acyclic chromatic index of G and is denoted by .In 1991, Alon et al. [N. Alon, C.J.H. McDiarmid, B.A. Reed, Acyclic coloring of graphs, Random Structures and Algorithms 2 (1991) 277-288] proved that for any graph G of maximum degree Δ(G). This bound was later improved to 16Δ(G) by Molloy and Reed in [M. Molloy, B. Reed, Further algorithmic aspects of the local lemma, in: Proceedings of the 30th Annual ACM Symposium on Theory of Computing, 1998, pp. 524-529].In this paper we prove that for a planar graph G without cycles of length three and that the same holds if G has an edge-partition into two forests. We also show that if G is planar.     

On induced-universal graphs for the class of bounded-degree graphs

For a family F of graphs, a graph U is said to be F-induced-universal if every graph of F is an induced subgraph of U. We give a construction for an induced-universal graph for the family of graphs on n vertices with degree at most k. For k even, our induced-universal graph has O(nk/2) vertices and for k odd it has O(n⌈k/2⌉−1/klog2+2/kn) vertices. This construction improves a result of Butler by a multiplicative constant factor for the even case and by almost a multiplicative n1/k factor for the odd case. We also construct induced-universal graphs for the class of oriented graphs with bounded incoming and outgoing degree, slightly improving another result of Butler.     

On transitive orientations with restricted covering graphs

We consider the problem of finding a transitive orientation of a comparability graph, such that the edge set of its covering graph contains a given subset of edges. We propose a solution which employs the classical technique of modular tree decomposition. The method leads to a polynomial time algorithm to construct such an orientation or report that it does not exist.     

On the bi-enhancement of chordal-bipartite probe graphs

Given a class C of graphs, a graph G=(V,E) is said to be a C-probe graph if there exists a stable (i.e., independent) set of vertices X⊆V and a set F of pairs of vertices of X such that the graph G^′=(V,E∪F) is in the class C. Recently, there has been increasing interest and research on a variety of C-probe graph classes, such as interval probe graphs, chordal probe graphs and chain probe graphs.In this paper we focus on chordal-bipartite probe graphs. We prove a structural result that if B is a bipartite graph with no chordless cycle of length strictly greater than 6, then B is chordal-bipartite probe if and only if a certain “enhanced” graph B^∗ is a chordal-bipartite graph. This theorem is analogous to a result on interval probe graphs in Zhang (1994) [18] and to one on chordal probe graphs in Golumbic and Lipshteyn (2004) [11].     

Maximum gap labelings of graphs

Given a graph, we define a base set to be a set of integers of size equal to the number of vertices in the graph. Given a graph and a base set, a labeling of the graph from the base set is an assignment of distinct integers from the base set to the vertices of the graph. The gap of an edge in a labeled graph is the absolute value of the difference between the labels of its endpoints. The gap of a labeled graph is the sum of the gaps of its edges.The maximum gap graph labeling problem takes as input a graph and a base set and maximizes the gap of the graph over all possible labelings from the base set. We show that this problem is NP-complete even when the base set is restricted to consecutive integers. We also show that this restricted case has polynomial time approximations that achieve a factor of 2/3 for trees, of 1/2 for bipartite graphs, and of 1/4 for general graphs, with a deterministic algorithm, while an expected factor of 1/3 for general graphs is achieved with a randomized algorithm. The case of general base sets is approximated within an expected factor of 1/16 for general graphs with a randomized polynomial time algorithm. We finally give a polynomial time algorithm that solves the maximum gap graph labeling problem for a graph that has bounded degree and bounded treewidth. The maximum graph labeling problem shows connections with the graceful tree conjecture.     

A note on 3-choosability of planar graphs

In this note, we prove that a planar graph is 3-choosable if it contains neither cycles of length 4, 7, and 9 nor 6-cycle with one chord. In particular, every planar graph without cycles of length 4, 6, 7, or 9 is 3-choosable. Together with other known parallel results, this completes a theorem on 3-choosability of planar graphs: planar graphs without cycles of length 4, i, j, 9 with i<j and i, j∈{5,6,7,8} are 3-choosable. Moreover, some further problems on this direction are proposed.     

On the number of Go positions on lattice graphs

We use transfer matrix methods to determine bounds for the numbers of legal Go positions for various numbers of players on some planar lattice graphs, including square lattice graphs such as those on which the game is normally played. We also find bounds on limiting constants that describe the behaviour of the number of legal positions on these lattice graphs as the dimensions of the lattices tend to infinity. These results amount to giving bounds for some specific evaluations of Go polynomials on these graphs.     

Connecting face hitting sets in planar graphs

We show that any face hitting set of size n of a connected planar graph with a minimum degree of at least 3 is contained in a connected subgraph of size 5n−6. Furthermore we show that this bound is tight by providing a lower bound in the form of a family of graphs. This improves the previously known upper and lower bound of 11n−18 and 3n respectively by Grigoriev and Sitters. Our proof is valid for simple graphs with loops and generalizes to graphs embedded in surfaces of arbitrary genus.     

On edge colorings of 1-planar graphs

A graph is 1-planar if it can be drawn on the plane so that each edge is crossed by at most one other edge. In this paper, it is shown that every 1-planar graph with maximum degree Δ?10 can be edge-colored with Δ colors.