Graph and Algorithms

This section is closed because it has been split into two new sections, Graph Theory and Discrete Algorithms

On-line ranking of split graphs

Borowiecki, Piotr ; Dereniowski, Dariusz.
A vertex ranking of a graph G is an assignment of positive integers (colors) to the vertices of G such that each path connecting two vertices of the same color contains a vertex of a higher color. Our main goal is to find a vertex ranking using as few colors as possible. Considering on-line […]

Hereditary biclique-Helly graphs: recognition and maximal biclique enumeration

Eguia, Martiniano ; Soulignac, Francisco Juan.
A biclique is a set of vertices that induce a complete bipartite graph. A graph G is biclique-Helly when its family of maximal bicliques satisfies the Helly property. If every induced subgraph of G is also biclique-Helly, then G is hereditary biclique-Helly. A graph is C4-dominated when every cycle […]

List edge and list total colorings of planar graphs without non-induced 7-cycles

Dong, Aijun ; Liu, Guizhen ; Li, Guojun.
Giving a planar graph G, let χ'l(G) and χ''l(G) denote the list edge chromatic number and list total chromatic number of G respectively. It is proved that if G is a planar graph without non-induced 7-cycles, then χ'l(G)≤Δ(G)+1 and χ''l(G)≤Δ(G)+2 where Δ(G)≥7.

A Branch-and-Reduce Algorithm for Finding a Minimum Independent Dominating Set

Gaspers, Serge ; Liedloff, Mathieu.
An independent dominating set D of a graph G = (V,E) is a subset of vertices such that every vertex in V \ D has at least one neighbor in D and D is an independent set, i.e. no two vertices of D are adjacent in G. Finding a minimum independent dominating set in a graph is an NP-hard problem. Whereas […]

Bounds for the minimum oriented diameter

Kurz, Sascha ; Laetsch, Martin.
We consider the problem of determining an orientation with minimum diameter MOD(G) of a connected and bridge-less graph G. In 2001 Fomin et al. discovered the relation MOD(G) <= 9 gamma(G) - 5 between the minimum oriented diameter and the size gamma(G) of a minimum dominating set. We improve their […]

Vertex-colouring edge-weightings with two edge weights

Khatirinejad, Mahdad ; Naserasr, Reza ; Newman, Mike ; Seamone, Ben ; Stevens, Brett.
An edge-weighting vertex colouring of a graph is an edge-weight assignment such that the accumulated weights at the vertices yields a proper vertex colouring. If such an assignment from a set S exists, we say the graph is S-weight colourable. It is conjectured that every graph with no isolated edge […]

On hamiltonian chain saturated uniform hypergraphs

Dudek, Aneta ; Zak, Andrzej.
We say that a hypergraph H is hamiltonian chain saturated if H does not contain a hamiltonian chain but by adding any new edge we create a hamiltonian chain in H. In this paper we ask about the smallest size of a k-uniform hamiltonian chain saturated hypergraph. We present a construction of a family […]

On neighbour-distinguishing colourings from lists

Horňák, Mirko ; WoźniaK, Mariusz.
An edge colouring of a graph is said to be neighbour-distinguishing if any two adjacent vertices have distinct sets of colours of their incident edges. In this paper the list version of the problem of determining the minimum number of colours in a neighbour-distinguishing colouring of a given graph […]

Some results on stable sets for k-colorable P₆-free graphs and generalizations

Mosca, Raffaele.
This article deals with the Maximum Weight Stable Set (MWS) problem (and some other related NP-hard problems) and the class of P-6-free graphs. The complexity status of MWS is open for P-6-free graphs and is open even for P-5-free graphs (as a long standing open problem). Several results are known […]

Binary Labelings for Plane Quadrangulations and their Relatives

Felsner, Stefan ; Huemer, Clemens ; Kappes, Sarah ; Orden, David.
Motivated by the bijection between Schnyder labelings of a plane triangulation and partitions of its inner edges into three trees, we look for binary labelings for quadrangulations (whose edges can be partitioned into two trees). Our labeling resembles many of the properties of Schnyder's one for […]

Cycle transversals in bounded degree graphs

Groshaus, Marina ; Hell, Pavol ; Klein, Sulamita ; Nogueira, Loana Tito ; Protti, Fábio.
In this work we investigate the algorithmic complexity of computing a minimum C(k)-transversal, i.e., a subset of vertices that intersects all the chordless cycles with k vertices of the input graph, for a fixed k \textgreater= 3. For graphs of maximum degree at most three, we prove that this […]

Random 2-SAT Solution Components and a Fitness Landscape

Pitman, Damien.
We describe a limiting distribution for the number of connected components in the subgraph of the discrete cube induced by the satisfying assignments to a random 2-SAT formula. We show that, for the probability range where formulas are likely to be satisfied, the random number of components […]

On packing of two copies of a hypergraph

Pilsniak, Monika ; WoźniaK, Mariusz.
A 2-packing of a hypergraph H is a permutation sigma on V (H) such that if an edge e belongs to epsilon(H), then sigma(e) does not belong to epsilon(H). Let H be a hypergraph of order n which contains edges of cardinality at least 2 and at most n - 2. We prove that if H has at most n - 2 edges then […]

Tree-width and large grid minors in planar graphs

Grigoriev, Alexander.
We show that for a planar graph with no g-grid minor there exists a tree-decomposition of width at most 5g - 6. The proof is constructive and simple. The underlying algorithm for the tree-decomposition runs in O(n(2) log n) time.

Parameterized Problems Related to Seidel's Switching

Jelinkova, Eva ; Suchy, Ondrej ; Hlineny, Petr ; Kratochvil, Jan.
Seidel's switching is a graph operation which makes a given vertex adjacent to precisely those vertices to which it was non-adjacent before, while keeping the rest of the graph unchanged. Two graphs are called switching-equivalent if one can be made isomorphic to the other by a sequence of switches. […]

Irregular edge coloring of 2-regular graphs

Cichacz, Sylwia ; Przybylo, Jakub.
Let G be a simple graph and let us color its edges so that the multisets of colors around each vertex are distinct. The smallest number of colors for which such a coloring exists is called the irregular coloring number of G and is denoted by c(G). We determine the exact value of the irregular […]

On the complexity of vertex-coloring edge-weightings

Dudek, Andrzej ; Wajc, David.
Given a graph G = (V; E) and a weight function omega : E -\textgreater R, a coloring of vertices of G, induced by omega, is defined by chi(omega) (nu) = Sigma(e(sic)nu) omega (e) for all nu is an element of V. In this paper, we show that determining whether a particular graph has a weighting of the […]

Colouring the Square of the Cartesian Product of Trees

Wood, David, .
We prove upper and lower bounds on the chromatic number of the square of the cartesian product of trees. The bounds are equal if each tree has even maximum degree.

On the Book Thickness of k-Trees

Dujmović, Vida ; Wood, David, .
Every k-tree has book thickness at most k + 1, and this bound is best possible for all k \textgreater= 3. Vandenbussche et al. [SIAM J. Discrete Math., 2009] proved that every k-tree that has a smooth degree-3 tree decomposition with width k has book thickness at most k. We prove this result is best […]

An expected polynomial time algorithm for coloring 2-colorable 3-graphs

Person, Yury ; Schacht, Mathias.
We present an algorithm that for 2-colorable 3-uniform hypergraphs, finds a 2-coloring in average running time O (n(5) log(2) n).

Avoidance colourings for small nonclassical Ramsey numbers

Burger, Alewyn Petrus ; Vuuren, Jan H., .
The irredundant Ramsey number s - s(m, n) [upper domination Ramsey number u - u(m, n), respectively] is the smallest natural number s [u, respectively] such that in any red-blue edge colouring (R, B) of the complete graph of order s [u, respectively], it holds that IR(B) \textgreater= m or IR(R) […]

8-star-choosability of a graph with maximum average degree less than 3

Chen, Min ; Raspaud, André ; Wang, Weifan.
A proper vertex coloring of a graphGis called a star-coloring if there is no path on four vertices assigned to two colors. The graph G is L-star-colorable if for a given list assignment L there is a star-coloring c such that c(v) epsilon L(v). If G is L-star-colorable for any list assignment L with […]

Acyclic colourings of graphs with bounded degree

Borowiecki, Mieczyslaw ; Fiedorowicz, Anna ; Jesse-Jozefczyk, Katarzyna ; Sidorowicz, Elzbieta.
A k-colouring of a graph G is called acyclic if for every two distinct colours i and j, the subgraph induced in G by all the edges linking a vertex coloured with i and a vertex coloured with j is acyclic. In other words, there are no bichromatic alternating cycles. In 1999 Boiron et al. conjectured […]

Split-critical and uniquely split-colorable graphs

Ekim, Tınaz ; Ries, Bernard ; De Werra, Dominique.
The split-coloring problem is a generalized vertex coloring problem where we partition the vertices into a minimum number of split graphs. In this paper, we study some notions which are extensively studied for the usual vertex coloring and the cocoloring problem from the point of view of […]

On a 1, 2 Conjecture

Przybylo, Jakub ; WoźniaK, Mariusz.
Let us assign positive integers to the edges and vertices of a simple graph G. As a result we obtain a vertex-colouring of G with integers, where a vertex colour is simply a sum of the weight assigned to the vertex itself and the weights of its incident edges. Can we obtain a proper colouring using […]

Linear Time Recognition Algorithms and Structure Theorems for Bipartite Tolerance Graphs and Bipartite Probe Interval Graphs

Brown, David E. ; Busch, Arthur H. ; Isaak, Garth.
A graph is a probe interval graph if its vertices can be partitioned into probes and nonprobes with an interval associated to each vertex so that vertices are adjacent if and only if their corresponding intervals intersect and at least one of them is a probe. A graph G = (V, E) is a tolerance graph […]

Coloring Geographical Threshold Graphs

Bradonjic, Milan ; Mueller, Tobias ; Percus, Allon G..
We propose a coloring algorithm for sparse random graphs generated by the geographical threshold graph (GTG) model, a generalization of random geometric graphs (RGG). In a GTG, nodes are distributed in a Euclidean space, and edges are assigned according to a threshold function involving the distance […]

Some properties of semiregular cages

Balbuena, Camino ; Marcote, Xavier ; Gonzalez-Moreno, Diego.
A graph with degree set \r, r + 1\ is said to be semiregular. A semiregular cage is a semiregular graph with given girth g and the least possible order. First, an upper bound on the diameter of semiregular graphs with girth g and order close enough to the minimum possible value is given in this […]

Lower Bounds on the Area Requirements of Series-Parallel Graphs

Frati, Fabrizio.
We show that there exist series-parallel graphs requiring Omega(n2(root log n)) area in any straight-line or poly-line grid drawing. Such a result is achieved in two steps. First, we show that, in any straight-line or poly-line drawing of K(2,n), one side of the bounding box has length Omega(n), […]

Convex Partitions of Graphs induced by Paths of Order Three

Centeno, C. C. ; Dantas, S. ; Dourado, M. C. ; Rautenbach, Dieter ; Szwarcfiter, Jayme Luiz.
A set C of vertices of a graph G is P(3)-convex if v is an element of C for every path uvw in G with u, w is an element of C. We prove that it is NP-complete to decide for a given graph G and a given integer p whether the vertex set of G can be partitioned into p non-empty disjoint P(3)-convex sets. […]

Covering codes in Sierpinski graphs

Beaudou, Laurent ; Gravier, Sylvain ; Klavžar, Sandi ; Kovse, Matjaz ; Mollard, Michel.
For a graph G and integers a and b, an (a, b)-code of G is a set C of vertices such that any vertex from C has exactly a neighbors in C and any vertex not in C has exactly b neighbors in C. In this paper we classify integers a and b for which there exist (a, b)-codes in Sierpinski graphs.

Edge-Removal and Non-Crossing Configurations in Geometric Graphs

Aichholzer, Oswin ; Cabello, Sergio ; Fabila-Monroy, Ruy ; Flores-Peñaloza, David ; Hackl, Thomas ; Huemer, Clemens ; Hurtado, Ferran ; Wood, David, .
A geometric graph is a graph G = (V, E) drawn in the plane, such that V is a point set in general position and E is a set of straight-line segments whose endpoints belong to V. We study the following extremal problem for geometric graphs: How many arbitrary edges can be removed from a complete […]

Spectral characterizations of sun graphs and broken sun graphs

Boulet, Romain.
Several matrices can be associated to a graph such as the adjacency matrix or the Laplacian matrix. The spectrum of these matrices gives some informations about the structure of the graph and the question ''Which graphs are determined by their spectrum?'' remains a difficult problem in algebraic […]

On economical set representations of graphs

Kong, Jing ; Wu, Yaokun.
In this paper we discuss the bounds of and relations among various kinds of intersection numbers of graphs. Especially, we address extremal graphs with respect to the established bounds. The uniqueness of the minimum-size intersection representations for some graphs is also studied. In the course of […]

Edge condition for long cycles in bipartite graphs

Adamus, Lech.
The following problem was solved by Woodall in 1972: for any pair of nonnegative integers n and k < n/2 - 1 find the minimum integer g(n, k) such that every graph with n vertices and at least g(n, k) edges contains a cycle of length n - k. Woodall proved even more: the size g(n, k), in fact, […]

Clique-transversal sets and weak 2-colorings in graphs of small maximum degree

Bacsó, Gábor ; Tuza, Zsolt.
A clique-transversal set in a graph is a subset of the vertices that meets all maximal complete subgraphs on at least two vertices. We prove that every connected graph of order n and maximum degree three has a clique-transversal set of size left perpendicular19n/30 + 2/15right perpendicular. This […]

Gray codes avoiding matchings

Dimitrov, Darko ; Dvořák, Tomáš ; Gregor, Petr ; Škrekovski, Riste.
A (cyclic) n-bit Gray code is a (cyclic) ordering of all 2(n) binary strings of length n such that consecutive strings differ in a single bit. Equivalently, an n-bit Gray code can be viewed as a Hamiltonian path of the n-dimensional hypercube Q(n), and a cyclic Gray code as a Hamiltonian cycle of […]

Adjoint functors and tree duality

Foniok, Jan ; Tardif, Claude.
A family T of digraphs is a complete set of obstructions for a digraph H if for an arbitrary digraph G the existence of a homomorphism from G to H is equivalent to the non-existence of a homomorphism from any member of T to G. A digraph H is said to have tree duality if there exists a complete set […]

Ore and Erdős type conditions for long cycles in balanced bipartite graphs

Adamus, Janusz ; Adamus, Lech.
We conjecture Ore and Erdős type criteria for a balanced bipartite graph of order 2n to contain a long cycle C(2n-2k), where 0 <= k < n/2. For k = 0, these are the classical hamiltonicity criteria of Moon and Moser. The main two results of the paper assert that our conjectures hold for k = 1 as […]

On the chromatic number of some flip graphs

Fabila-Monroy, Ruy ; Flores-Peñaloza, David ; Huemer, Clemens ; Hurtado, Ferran ; Urrutia, Jorge ; Wood, David, .
This paper studies the chromatic number of the following four flip graphs (under suitable definitions of a flip): the flip graph of perfect matchings of a complete graph of even order, the flip graph of triangulations of a convex polygon (the associahedron), the flip graph of non-crossing […]

Long cycles in hypercubes with distant faulty vertices

Gregor, Petr ; Škrekovski, Riste.
In this paper, we study long cycles in induced subgraphs of hypercubes obtained by removing a given set of faulty vertices such that every two faults are distant. First, we show that every induced subgraph of Q(n) with minimum degree n - 1 contains a cycle of length at least 2(n) - 2(f) where f is […]

Self-complementing permutations of k-uniform hypergraphs

Szymański, Artur ; Wojda, Adam Pawel.
A k-uniform hypergraph H = ( V; E) is said to be self-complementary whenever it is isomorphic with its complement (H) over bar = ( V; ((V)(k)) - E). Every permutation sigma of the set V such that sigma(e) is an edge of (H) over bar if and only if e is an element of E is called self-complementing. […]

Independent sets in (P₆, diamond)-free graphs

Mosca, Raffaele.
We prove that on the class of (P6,diamond)-free graphs the Maximum-Weight Independent Set problem and the Minimum-Weight Independent Dominating Set problem can be solved in polynomial time.

Bounds for minimum feedback vertex sets in distance graphs and circulant graphs

Kheddouci, Hamamache ; Togni, Olivier.
For a set D ⊂ Zn, the distance graph Pn(D) has Zn as its vertex set and the edges are between vertices i and j with |i − j| ∈ D. The circulant graph Cn(D) is defined analogously by considering operations modulo n. The minimum feedback vertex set problem consists in finding the smallest number of […]

On the size of induced acyclic subgraphs in random digraphs

Spencer, Joel ; Subramanian, C.R..
Let D ∈ D(n, p) denote a simple random digraph obtained by choosing each of the (n 2) undirected edges independently with probability 2p and then orienting each chosen edge independently in one of the two directions with equal probability 1/2. Let mas(D) denote the maximum size of an induced acyclic […]

On the k-restricted structure ratio in planar and outerplanar graphs

Călinescu, Gruia ; Fernandes, Cristina G..
A planar k-restricted structure is a simple graph whose blocks are planar and each has at most k vertices. Planar k-restricted structures are used by approximation algorithms for Maximum Weight Planar Subgraph, which motivates this work. The planar k-restricted ratio is the infimum, over simple […]

On-line Ramsey numbers for paths and stars

Grytczuk, J. A. ; Kierstead, H. A. ; Prałat, P..
We study on-line version of size-Ramsey numbers of graphs defined via a game played between Builder and Painter: in one round Builder joins two vertices by an edge and Painter paints it red or blue. The goal of Builder is to force Painter to create a monochromatic copy of a fixed graph H in as few […]

Progress on the traceability conjecture for oriented graphs

Frick, Marietjie ; Katrenič, Peter.
A digraph is k-traceable if each of its induced subdigraphs of order k is traceable. The Traceability Conjecture is that for k ≥ 2 every k-traceable oriented graph of order at least 2k − 1 is traceable. The conjecture has been proved for k ≤ 5. We prove that it also holds for k = 6.

A note on compact and compact circular edge-colorings of graphs

Dereniowski, Dariusz ; Nadolski, Adam.
We study two variants of edge-coloring of edge-weighted graphs, namely compact edge-coloring and circular compact edge-coloring. First, we discuss relations between these two coloring models. We prove that every outerplanar bipartite graph admits a compact edge-coloring and that the decision problem […]

Total domination in K₅- and K₆-covered graphs

Favaron, Odile ; Karami, H. ; Sheikholeslami, S. M..
A graph G is Kr-covered if each vertex of G is contained in a Kr-clique. Let $\gamma_t(G)$ denote the total domination number of G. It has been conjectured that every Kr-covered graph of order n with no Kr-component satisfies $\gamma_t(G) \le \frac{2n}{r+1}$. We prove that this conjecture is true for […]

Bounded-degree graphs have arbitrarily large queue-number

Wood, David, .
It is proved that there exist graphs of bounded degree with arbitrarily large queue-number. In particular, for all \Delta ≥ 3 and for all sufficiently large n, there is a simple \Delta-regular n-vertex graph with queue-number at least c√\Delta_n^{1/2-1/\Delta} for some absolute constant c.

Extremal K_(s,t)-free bipartite graphs

Balbuena, Camino ; García-Vázquez, P. ; Marcote, Xavier ; Valenzuela, J. C..
In this paper new exact values of the Zarankiewicz function z(m,n;s,t) are obtained assuming certain requirements on the parameters. Moreover, all the corresponding extremal graphs are characterized. Finally, an extension of this problem to 3-partite graphs is studied.

The Laplacian spread of a tree

Fan, Yi-Zheng ; Xu, Jing ; Wang, Yi ; Liang, Dong.
The Laplacian spread of a graph is defined to be the difference between the largest eigenvalue and the second smallest eigenvalue of the Laplacian matrix of the graph. In this paper, we show that the star is the unique tree with maximal Laplacian spread among all trees of given order, and the path […]

On hereditary Helly classes of graphs

Groshaus, Marina ; Szwarcfiter, Jayme Luiz.
In graph theory, the Helly property has been applied to families of sets, such as cliques, disks, bicliques, and neighbourhoods, leading to the classes of clique-Helly, disk-Helly, biclique-Helly, neighbourhood-Helly graphs, respectively. A natural question is to determine for which graphs the […]

Bounds for minimum feedback vertex sets in distance graphs and circulant graphs

Kheddouci, Hamamache ; Togni, Olivier.
For a set D ⊂ Zn, the distance graph Pn(D) has Zn as its vertex set and the edges are between vertices i and j with |i − j| ∈ D. The circulant graph Cn(D) is defined analogously by considering operations modulo n. The minimum feedback vertex set problem consists in finding the smallest number of […]

Recurrence among trees with most numerous efficient dominating sets

Bród, Dorota ; Skupień, Zdzis\law.
A dominating set D of vertices in a graph G is called an efficient dominating set if the distance between any two vertices in D is at least three. A tree T of order n is called maximum if T has the largest number of efficient dominating sets among all n-vertex trees. A constructive characterization […]

On the complexity of the balanced vertex ordering problem

Kára, Jan ; Kratochvil, Jan ; Wood, David, .
We consider the problem of finding a balanced ordering of the vertices of a graph. More precisely, we want to minimise the sum, taken over all vertices v, of the difference between the number of neighbours to the left and right of v. This problem, which has applications in graph drawing, was […]

Approximation and inapproximability results on balanced connected partitions of graphs

Chataigner, Frédéric ; Salgado, Liliane R. B. ; Wakabayashi, Yoshiko.
Let G=(V,E) be a connected graph with a weight function w: V \to \mathbbZ₊, and let q ≥q 2 be a positive integer. For X⊆ V, let w(X) denote the sum of the weights of the vertices in X. We consider the following problem on G: find a q-partition P=(V₁,V₂, \ldots, V_q) of V such that G[V_i] is […]

Independent sets in graphs with an excluded clique minor

Wood, David, .
Let G be a graph with n vertices, with independence number α, and with no Kt+1-minor for some t ≥ 5. It is proved that (2α - 1)(2t - 5) ≥ 2n - 5. This improves upon the previous best bound whenever n≥2/5t2.

Complexity results on graphs with few cliques

Rosgen, Bill ; Stewart, Lorna.
A graph class has few cliques if there is a polynomial bound on the number of maximal cliques contained in any member of the class. This restriction is equivalent to the requirement that any graph in the class has a polynomial sized intersection representation that satisfies the Helly property. On […]

A lower bound for approximating the Grundy number

Kortsarz, Guy.
The grundy numbering of a graph is the maximum number of colors used by on-line first-fit coloring, under the worst order of arrival of vertices. The grundy numbering problem is to find this ordering. We prove that there is a constant c>1 so that approximating the grundy numbering problem within c […]

Tribes of cubic partial cubes

Klavžar, Sandi ; Shpectorov, Sergey.
Partial cubes are graphs isometrically embeddable into hypercubes. Three infinite families and a few sporadic examples of cubic partial cubes are known. The concept of a tribe is introduced as means to systematize the known examples and establish relations among them. Efficient methods of […]

Probe split graphs

Le, Van Bang ; Ridder, H. N., .
An undirected graph G=(V,E) is a probe split graph if its vertex set can be partitioned into two sets, N (non-probes) and P (probes) where N is independent and there exists E' ⊆ N× N such that G'=(V,E∪ E') is a split graph. Recently Chang et al. gave an O(V4(V+E)) time recognition algorithm for […]

On the kth Eigenvalues of Trees with Perfect Matchings

Chang, An ; Shiu, Wai Chee.
Résumé comportant des formules mathématiques, disponible sur le ficher pdf / Abstract with mathematical formulas, available on pdf file.

Strong chromatic index of products of graphs

Togni, Olivier.
The strong chromatic index of a graph is the minimum number of colours needed to colour the edges in such a way that each colour class is an induced matching. In this paper, we present bounds for strong chromatic index of three different products of graphs in term of the strong chromatic index of […]