Vol. 16 no. 3


1. A four-sweep LBFS recognition algorithm for interval graphs

Li, Peng ; Wu, Yaokun.
In their 2009 paper, Corneil et al. design a linear time interval graph recognition algorithm based on six sweeps of Lexicographic Breadth-First Search (LBFS) and prove its correctness. They believe that their corresponding 5-sweep LBFS interval graph recognition algorithm is also correct. Thanks to […]
Section: Graph Theory

2. Balancedness of subclasses of circular-arc graphs

Bonomo, Flavia ; Duran, Guillermo ; Safe, Martın D. ; Wagler, Annegret K..
A graph is balanced if its clique-vertex incidence matrix contains no square submatrix of odd order with exactly two ones per row and per column. There is a characterization of balanced graphs by forbidden induced subgraphs, but no characterization by mininal forbidden induced subgraphs is known, […]
Section: Graph Theory

3. Complexity of conditional colouring with given template

Dukes, Peter J. ; Lowdon, Steve ; Macgillivray, Gary.
We study partitions of the vertex set of a given graph into cells that each induce a subgraph in a given family, and for which edges can have ends in different cells only when those cells correspond to adjacent vertices of a fixed template graph H. For triangle-free templates, a general collection […]
Section: Graph Theory

4. Oriented diameter and rainbow connection number of a graph

Huang, Xiaolong ; Li, Hengzhe ; Li, Xueliang ; Sun, Yuefang.
The oriented diameter of a bridgeless graph G is min diam(H) | H is a strang orientation of G. A path in an edge-colored graph G, where adjacent edges may have the same color, is called rainbow if no two edges of the path are colored the same. The rainbow connection number rc(G) of G is the smallest […]
Section: Graph Theory

5. An exact algorithm for the generalized list T-coloring problem

Junosza-Szaniawski, Konstanty ; Rzazewski, Pawel.
The generalized list T-coloring is a common generalization of many graph coloring models, including classical coloring, L(p,q)-labeling, channel assignment and T-coloring. Every vertex from the input graph has a list of permitted labels. Moreover, every edge has a set of forbidden differences. We […]
Section: Discrete Algorithms

6. On permutation complexity of fixed points of some uniform binary morphisms

Valyuzhenich, Alexandr.
We study properties of infinite permutations generated by fixed points of some uniform binary morphisms, and find the formula for their complexity.
Section: Combinatorics

7. Biased weak polyform achievement games

Norris, Ian ; Sieben, Nándor.
In a biased weak (a,b) polyform achievement game, the maker and the breaker alternately mark a,b previously unmarked cells on an infinite board, respectively. The maker's goal is to mark a set of cells congruent to a polyform. The breaker tries to prevent the maker from achieving this goal. A […]
Section: Combinatorics

8. Genus distributions of cubic series-parallel graphs

Gross, Jonathan L. ; Kotrbčík, Michal ; Sun, Timothy.
We derive a quadratic-time algorithm for the genus distribution of any 3-regular, biconnected series-parallel graph, which we extend to any biconnected series-parallel graph of maximum degree at most 3. Since the biconnected components of every graph of treewidth 2 are series-parallel graphs, this […]
Section: Graph Theory

9. Bounding the monomial index and (1,l)-weight choosability of a graph

Seamone, Ben.
Let G = (V,E) be a graph. For each e ∈E(G) and v ∈V(G), let Le and Lv, respectively, be a list of real numbers. Let w be a function on V(G) ∪E(G) such that w(e) ∈Le for each e ∈E(G) and w(v) ∈Lv for each v ∈V(G), and let cw be the vertex colouring obtained by cw(v) = w(v) + ∑ₑ ∋vw(e). A graph is […]
Section: Graph Theory

10. Partitioning the vertex set of a bipartite graph into complete bipartite subgraphs

Duginov, Oleg.
Given a graph and a positive integer k, the biclique vertex-partition problem asks whether the vertex set of the graph can be partitioned into at most k bicliques (connected complete bipartite subgraphs). It is known that this problem is NP-complete for bipartite graphs. In this paper we investigate […]
Section: Graph Theory

11. Packing and covering the balanced complete bipartite multigraph with cycles and stars

Lee, Hung-Chih.
Let Ck denote a cycle of length k and let Sk denote a star with k edges. For multigraphs F, G and H, an (F,G)-decomposition of H is an edge decomposition of H into copies of F and G using at least one of each. For L⊆H and R⊆rH, an (F,G)-packing (resp. (F,G)-covering) of H with leave L (resp. padding […]
Section: Graph Theory

12. On the number of regular edge labelings

Buchin, Kevin ; Speckmann, Bettina ; Verdonschot, Sander.
We prove that any irreducible triangulation on n vertices has O(4.6807n) regular edge labelings and that there are irreducible triangulations on n vertices with Ω(3.0426n) regular edge labelings. Our upper bound relies on a novel application of Shearer's entropy lemma. As an example of the wider […]
Section: Combinatorics

13. Toppling numbers of complete and random graphs

Bonato, Anthony ; Kinnersley, William B. ; Pralat, Pawel.
We study a two-person game played on graphs based on the widely studied chip-firing game. Players Max and Min alternately place chips on the vertices of a graph. When a vertex accumulates as many chips as its degree, it fires, sending one chip to each neighbour; this may in turn cause other vertices […]
Section: Graph Theory

14. Generalized dynamic storage allocation

Kierstead, H. A. ; Saoub, Karin R..
Dynamic Storage Allocation is a problem concerned with storing items that each have weight and time restrictions. Approximate algorithms have been constructed through online coloring of interval graphs. We present a generalization that uses online coloring of tolerance graphs. We utilize […]
Section: Graph Theory

15. Partitioning Harary graphs into connected subgraphs containing prescribed vertices

Baudon, Olivier ; Bensmail, Julien ; Sopena, Eric.
A graph G is arbitrarily partitionable (AP for short) if for every partition (tau_1, ..., tau_p) of |V(G)| there exists a partition (V_1, ..., V_p) of V(G) such that each V_i induces a connected subgraph of G with order tau_i. If, additionally, each of k of these subgraphs contains an arbitrary […]

16. An algorithmic analysis of Flood-It and Free-Flood-It on graph powers

Souza, Uéverton dos Santos ; Protti, Fábio ; Silva, Maise, .
Flood-it is a combinatorial game played on a colored graph G whose aim is to make the graph monochromatic using the minimum number of flooding moves, relatively to a fixed pivot. Free-Flood-it is a variant where the pivot can be freely chosen for each move of the game. The standard versions of […]
Section: Analysis of Algorithms

17. On the numbers of radial orderings of planar point sets

Dıaz-Banez, José Miguel ; Fabila-Monroy, Ruy ; Pérez-Lantero, Pablo.
Given a set S of n points in the plane, a radial ordering of S with respect to a point p (not in S) is a clockwise circular ordering of the elements in S by angle around p. If S is two-colored, a colored radial ordering is a radial ordering of S in which only the colors of the points are considered. […]
Section: Combinatorics

18. Determining pure discrete spectrum for some self-affine tilings

Akiyama, Shigeki ; Gähler, Franz ; Lee, Jeong-Yup.
By the algorithm implemented in the paper by Akiyama-Lee [Adv. Math. 226(4):2855 13;2883, 2011] and some of its predecessors, we have examined the pure discreteness of the spectrum for all irreducible Pisot substitutions of trace less than or equal to 2, and some cases of planar tilings generated by […]
Section: Discrete Algorithms

19. Cell-paths in mono- and bichromatic line arrangements in the plane

Aichholzer, Oswin ; Cardinal, Jean ; Hackl, Thomas ; Hurtado, Ferran ; Korman, Matias ; Pilz, Alexander ; Silveira, Rodrigo I. ; Uehara, Ryuhei ; Valtr, Pavel ; Vogtenhuber, Birgit et al.
We prove that the dual graph of any arrangement of n lines in general position always contains a path of length at least n2/4. Further, we show that in every arrangement of n red and blue lines — in general position and not all of the same color — there is a simple path through at least n cells […]
Section: Combinatorics

20. Detection number of bipartite graphs and cubic graphs

Havet, Frederic ; Paramaguru, Nagarajan ; Sampathkumar, Rathinaswamy.
For a connected graph G of order |V(G)| ≥3 and a k-labelling c : E(G) →{1,2,…,k} of the edges of G, the code of a vertex v of G is the ordered k-tuple (ℓ1,ℓ2,…,ℓk), where ℓi is the number of edges incident with v that are labelled i. The k-labelling c is detectable if every two adjacent vertices of […]