3 papers
math.CO2016
Regular colorings and factors of regular graphs
Anton Bernshteyn, Omid Khormali, Ryan R. Martin +4
An -coloring of an -regular graph is an edge coloring such that each vertex is incident to edges of one color and edge of a different color. In this paper…
math.CO2016
Chromatic number of ordered graphs with forbidden ordered subgraphs
Maria Axenovich, Jonathan Rollin, Torsten Ueckerdt
It is well-known that the graphs not containing a given graph H as a subgraph have bounded chromatic number if and only if H is acyclic. Here we consider ordered graphs, i.e., grap…
math.CO2012
Cubic Augmentation of Planar Graphs
Tanja Hartmann, Jonathan Rollin, Ignaz Rutter
In this paper we study the problem of augmenting a planar graph such that it becomes 3-regular and remains planar. We show that it is NP-hard to decide whether such an augmentation…