#planar graphs
13 resultsPlanar Graphs of Bounded Degree have Constant Queue Number
Michael A. Bekos, Henry Förster, Martin Gronemann +4
The authors prove that planar graphs with bounded degree have a constant (bounded) queue number, which also yields constant‑volume three‑dimensional straight‑line grid drawings and…
Generalization of some results on list coloring and DP-coloring
Keaitsuda Maneeruk Nakprasit, Kittikorn Nakprasit
The paper introduces DPG‑coloring, combining DP‑coloring and variable degeneracy, and uses it to extend several known results on list coloring and DP‑coloring of planar graphs.
Local and Union Page Numbers
Laura Merker, Torsten Ueckerdt
The paper introduces two new graph parameters, the local page number and the union page number, which relax the classic page number by focusing on per‑vertex page usage and vertex‑…
Parameterized Algorithms for Maximum Cut with Connectivity Constraints
Hiroshi Eto, Tesshu Hanaka, Yasuaki Kobayashi +1
The paper investigates two variants of the Maximum Cut problem that require additional connectivity conditions, proving their NP-completeness on several graph classes and presentin…
Circle patterns and critical Ising models
Marcin Lis
The paper introduces a new class of planar Ising models whose dual graphs form circle patterns and proves that these models are magnetically critical, generalizing the known critic…
Planar graphs with girth at least 5 are (3,4)-colorable
Ilkyoo Choi, Gexin Yu, Xia Zhang
The paper proves that every planar graph whose cycles have length at least five can have its vertices partitioned into two sets so that one induces a subgraph of maximum degree 3 a…
Greedy Rectilinear Drawings
Patrizio Angelini, Michael A. Bekos, Walter Didimo +6
The paper studies graph drawings where edges are axis-aligned (horizontal or vertical) and the drawing is greedy, meaning one can always move closer to a target vertex along a path…
Colouring of generalized signed planar graphs
Ligang Jin, Tsai-Lien Wong, Xuding Zhu
The paper investigates a unified framework for graph colourings defined by permutation assignments on arcs, characterizes which subsets of the permutation group S₄ can colour every…
A refinement of choosability of graphs
Xuding Zhu
The paper introduces λ‑choosability, a refined version of list‑coloring based on partitions of the list size, establishes its hierarchical relationship with other partitions, and e…
Finite groups with planar generating graph
Andrea Lucchini
The paper classifies all finite 2‑generated groups whose generating graph is planar, showing that only a short list of small groups (e.g., C₂, C₃, C₄, C₅, C₆, C₂×C₂, D₃, D₄, Q₈, C₄…
On fractional fragility rates of graph classes
ZdenÄk DvoÅák, Jean-Sébastien Sereni
The paper studies probability distributions on vertex subsets of graphs where each vertex is included with probability at most 1/a, and shows that for any planar graph one can dele…
Bounding the number of cycles in a graph in terms of its degree sequence
ZdenÄk DvoÅák, Natasha Morrison, Jonathan A. Noel +2
The paper provides an upper bound on how many cycles a simple graph can have based on its degree sequence, and uses this result to settle several conjectures and improve bounds for…
The interval number of a planar graph is at most three
Guillaume Guégan, Kolja Knauer, Jonathan Rollin +1
The paper presents a new, shorter proof that any planar graph can be represented as the intersection graph of at most three intervals per vertex, confirming that the interval numbe…